{"ID":2886724,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.02108","arxiv_id":"2508.02108","title":"Monotone Paths on Acyclic 3-Regular Graphs","abstract":"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+\\varphi)^n$, with $\\varphi$ 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 $\\varphi^n$.","short_abstract":"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+\\varphi)^n$, with $\\...","url_abs":"https://arxiv.org/abs/2508.02108","url_pdf":"https://arxiv.org/pdf/2508.02108v1","authors":"[\"François Clément\",\"Dan Guyer\"]","published":"2025-08-04T06:37:13Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"math.OC\"]","methods":"[]","has_code":false}