2025/04/29 by Martina Juhnke, Juhnke, Martina, Germain Poullot +1 · 1 citation
Computer Science · Mathematics · #52B05 #52B11 #52B12 #90C05 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Point processes and geometric inequalities #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2504.20739
openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
To solve a linear program, the simplex method follows a path in the graph of a polytope, on which a linear function increases. The length of this path is an key measure of the complexity of the simplex method. Numerous previous articles focused on the longest paths, or, following Borgwardt, computed the average length of a path for certain random polytopes. We detail more precisely how this length is distributed, i.e., how many paths of each length there are. It was conjectured by De Loera that the number of paths counted according to their length forms a unimodal sequence. We give examples (old and new) for which this holds; but we disprove this conjecture by constructing counterexamples for several classes of polytopes. However, De Loera is "statistically correct": We prove that the length of coherent paths on a random polytope (with vertices chosen uniformly on a sphere) admits a central limit theorem.