标题： 单调路径在无环三正则图上 显示英文标题

标题： Monotone Paths on Acyclic 3-Regular Graphs

摘要： 受试图理解单纯形法行为的启发，Athanasiadis、De Loera 和 Zhang 给出了 3-多面体上单调路径数量的上下界。对于具有$2n$个顶点的简单 3-多面体，他们证明了单调路径的数量上限为$(1+\varphi)^n$，其中$\varphi$是黄金比例。我们改进了这一结果，并表明对于一个更大的图类，数量上限为$c \cdot 1.6779^n$，其中$c$是某个通用常数。同时，目前已知的最佳构造和猜想的极值器约为$\varphi^n$。 显示英文摘要

摘要： 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$.