Enumerative problems for arborescences and monotone paths on polytope graphs. (English) Zbl 1522.05152
Summary: Every generic linear functional \(f\) on a convex polytope \(P\) induces an orientation on the graph of \(P\). From the resulting directed graph one can define a notion of \(f\)-arborescence and \(f\)-monotone path on \(P\), as well as a natural graph structure on the vertex set of \(f\)-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of \(f\)-arborescences, the number of \(f\)-monotone paths, and the diameter of the graph of \(f\)-monotone paths for polytopes \(P\) in terms of their dimension and number of vertices or facets.
{© 2021 Wiley Periodicals LLC}
{© 2021 Wiley Periodicals LLC}
Software:
OEISOnline Encyclopedia of Integer Sequences:
Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1.References:
| [1] | C. A.Athanasiadis, Piles of cubes, monotone path polytopes, and hyperplane arrangements, Discrete Comput. Geom. 21 (1999), no. 1, 117-130. https://doi.org/10.1007/PL00009404 · Zbl 0979.52002 · doi:10.1007/PL00009404 |
| [2] | C. A.Athanasiadis, J. A.De Loera, V.Reiner, and F.Santos, Fiber polytopes for the projections between cyclic polytopes, European J. Combin. 21 (2000), 19-47. · Zbl 0952.52010 |
| [3] | C. A.Athanasiadis, P. H.Edelman, and V.Reiner, Monotone paths on polytopes, Math. Z. 235 (2000), 549-555. |
| [4] | C. A.Athanasiadis and F.Santos, Monotone paths on zonotopes and oriented matroids, Canad. J. Math. 53 (2001), no. 6, 1121-1140. https://doi.org/10.4153/CJM-2001-042-3 · Zbl 1003.52008 · doi:10.4153/CJM-2001-042-3 |
| [5] | D.Barnette, A proof of the lower bound conjecture for convex polytopes, Pacific J. Math. 46 (1973), 349-354. https://oeis.org/ · Zbl 0264.52006 |
| [6] | L. J.Billera, M. M.Kapranov, and B.Sturmfels, Cellular strings on polytopes, Proc. Am. Math. Soc.122 (1994), no. 2, 549-555. · Zbl 0812.52007 |
| [7] | L. J.Billera and B.Sturmfels, Fiber polytopes, Ann. of Math. 135 (1992), no. 3, 527-549. · Zbl 0762.52003 |
| [8] | A.Björner, M.LasVergnas, B.Sturmfels, N.White, and G. M.Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, 2nd ed., vol. 46, Cambridge University Press, Cambridge, 1999. https://doi.org/10.1017/CBO9780511586507 · Zbl 0944.52006 · doi:10.1017/CBO9780511586507 |
| [9] | M.Blanchard, J. A.De Loera, and Q.Louveaux, On the length of monotone paths in polyhedra. In preparation. · Zbl 1470.52014 |
| [10] | R.Cordovil and M. L.Moreira, A homotopy theorem on oriented matroids, Discrete Math. 111 (1993), no. 1, 131-136. http://www.sciencedirect.com/science/article/pii/0012365X9390149N, https://doi.org/10.1016/0012-365X(93)90149-N · Zbl 0781.52008 · doi:10.1016/0012-365X(93)90149-N |
| [11] | D.Dadush and N.Hähnle, On the shadow simplex method for curved polyhedra, Discrete Comput. Geom. 56 (2016), no. 4, 882-909. https://doi.org/10.1007/s00454-016-9793-3 · Zbl 1377.90055 · doi:10.1007/s00454-016-9793-3 |
| [12] | M.Develin, LP‐orientations of cubes and crosspolytopes, Adv. Geom. 4 (2004), no. 4, 459-468. https://doi.org/10.1515/advg.2004.4.4.459 · Zbl 1067.52012 · doi:10.1515/advg.2004.4.4.459 |
| [13] | R.Edman, P.Jiradilok, G.Liu, and T.McConville, Zonotopes whose cellular strings are all coherent, Eur. J. Comb. 96 (2021). https://doi.org/10.1016/j.ejc.2021.103352 · Zbl 1466.52016 · doi:10.1016/j.ejc.2021.103352 |
| [14] | R. B.Edman, Diameter and coherence of monotone path graphs in low corank, Ph.D. thesis, May 2015. https://www-users.math.umn.edu/ reiner/edman-thesis.pdf |
| [15] | G.Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), no. 1, 125-151. https://doi.org/10.1007/BF01405094 · Zbl 0624.52004 · doi:10.1007/BF01405094 |
| [16] | J.McDonald, Fiber polytopes and fractional power series, J. Pure Appl. Algebra. 104 (1995), no. 2, 213-233. https://doi.org/10.1016/0022-4049(94)00129-5 · Zbl 0842.52009 · doi:10.1016/0022-4049(94)00129-5 |
| [17] | P.McMullen, Triangulations of simplicial polytopes, Beiträge Algebra Geom. 45 (2004), no. 1, 37-46. · Zbl 1081.52011 |
| [18] | J.Mihalisin and V.Klee, Convex and linear orientations of polytopal graphs, Discrete Comput. Geom. 24 (2000), no. 2-3, 421-435. https://doi.org/10.1007/s004540010046 · Zbl 0956.05048 · doi:10.1007/s004540010046 |
| [19] | S.Murai and E.Nevo, On the generalized lower bound conjecture for polytopes and spheres, Acta Math. 210 (2013), no. 1, 185-202. https://doi.org/10.1007/s11511-013-0093-y · Zbl 1279.52014 · doi:10.1007/s11511-013-0093-y |
| [20] | L.Pournin, The diameter of associahedra, Adv. Math.259 (2014), 13-42. https://doi.org/10.1016/j.aim.2014.02.035 · Zbl 1292.52011 · doi:10.1016/j.aim.2014.02.035 |
| [21] | L.Pournin, The asymptotic diameter of cyclohedra, Israel J. Math.219 (2017), no. 2, 609-635. https://doi.org/10.1007/s11856-017-1492-0 · Zbl 1371.52010 · doi:10.1007/s11856-017-1492-0 |
| [22] | V.Reiner and Y.Roichman, Diameter of graphs or reduced words and galleries, Trans. Amer. Math. Soc365 (2013), no. 5, 2779-2802. · Zbl 1333.20042 |
| [23] | A.Schrijver, Theory of linear and integer programming, Wiley‐Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., Hoboken, New Jersey, 1986. A Wiley‐Interscience Publication. · Zbl 0665.90063 |
| [24] | N. J. A.Sloane, The on‐line encyclopedia of integer sequences. https://oeis.org/ · Zbl 1044.11108 |
| [25] | G. M.Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer‐Verlag, New York, 1995. https://doi.org/10.1007/978-1-4613-8431-1 · Zbl 0823.52002 · doi:10.1007/978-1-4613-8431-1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
