Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.02108 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911090203426816 |
|---|---|
| author | Clément, François Guyer, Dan |
| author_facet | Clément, François Guyer, Dan |
| contents | Motivated by trying to understand the behavior of the simplex method, Athanasiadis, De Loera and Zhang provided upper and lower bounds on the number of the monotone paths on 3-polytopes. For simple 3-polytopes with $2n$ vertices, they showed that the number of monotone paths is bounded above by $(1+φ)^n$, with $φ$ being the golden ratio. We improve the result and show that for a larger family of graphs the number is bounded above by $c \cdot 1.6779^n$ for some universal constant $c$. Meanwhile, the best known construction and conjectured extremizer is approximately $φ^n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02108 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monotone Paths on Acyclic 3-Regular Graphs Clément, François Guyer, Dan Combinatorics Optimization and Control Motivated by trying to understand the behavior of the simplex method, Athanasiadis, De Loera and Zhang provided upper and lower bounds on the number of the monotone paths on 3-polytopes. For simple 3-polytopes with $2n$ vertices, they showed that the number of monotone paths is bounded above by $(1+φ)^n$, with $φ$ being the golden ratio. We improve the result and show that for a larger family of graphs the number is bounded above by $c \cdot 1.6779^n$ for some universal constant $c$. Meanwhile, the best known construction and conjectured extremizer is approximately $φ^n$. |
| title | Monotone Paths on Acyclic 3-Regular Graphs |
| topic | Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2508.02108 |