On 2-level polytopes arising in combinatorial settings. (English) Zbl 1395.52018
Summary: \(2\)-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some \(2\)-level polytopes arising in combinatorial settings. Our first contribution is proving that \(f_0(P)f_{d-1}(P)\leq d2^{d+1}\) for a large collection of families of such polytopes \(P\). Here \(f_0(P)\) (resp., \(f_{d-1}(P)\)) is the number of vertices (resp., facets) of \(P\), and \(d\) is its dimension. Whether this holds for all 2-level polytopes was asked in [A. Bohn et al., Lect. Notes Comput. Sci. 9294, 191–202 (2015; Zbl 1394.52008)], and experimental results from S. Fiorini et al. [ibid. 9849, 285–296 (2016; Zbl 1397.52008)] showed it true for \(d\leq 7\). The key to most of our proofs is a deeper understanding of the relations among those polytopes and their underlying combinatorial structure. This leads to a number of results that we believe to be of independent interest: a trade-off formula for the number of cliques and stable sets in a graph, a description of stable matching polytopes as affine projections of certain order polytopes, and a linear-size description of the base polytope of matroids that are 2-level in terms of cuts of an associated tree.
MSC:
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Software:
2L_enumReferences:
| [1] | M. Aprile, A. Cevallos, and Y. Faenza, On vertices and facets of combinatorial 2-level polytopes, in Proceedings of the 4th International Symposium on Combinatorial Optimization, Springer, Cham, Switzerland, 2016, pp. 177–188. · Zbl 1452.90324 |
| [2] | M. Aprile, Y. Faenza, S. Fiorini, T. Huynh, and M. Macchia, Extension complexity of stable set polytopes of bipartite graphs, in Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017, Revised Selected Papers, H. L. Bodlaender, G. J. Woeginger, eds., Springer International Publishing, Cham, Switzerland, 2017, pp. 75–87. · Zbl 1483.90129 |
| [3] | F. Barahona and M. Grötschel, On the cycle polytope of a binary matroid, J. Combin. Theory Ser. B, 40 (1986), pp. 40–62. · Zbl 0596.05018 |
| [4] | I. Bárány and A. Pór, On 0–1 polytopes with many facets, Adv. Math., 161 (2001), pp. 209–228. · Zbl 0988.52014 |
| [5] | R. E. Bixby and W. H. Cunningham, Matroid Optimization and Algorithms, MIT Press, Cambridge, MA, 1996. · Zbl 0848.05017 |
| [6] | A. Bohn, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich, Enumeration of 2-level polytopes, in Algorithms–ESA 2015, N. Bansal, I. Finocchi, eds., Lecture Notes in Computer Science 9294, Springer, Berlin, 2015, pp. 191–202. · Zbl 1394.52008 |
| [7] | A. Bohn, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich, Enumeration of 2-level polytopes, Math. Program. Comput., to appear. · Zbl 1394.52008 |
| [8] | F. Buekenhout and M. Parker, The number of nets of the regular convex polytopes in dimension \(≤\) 4, Discrete Math., 186 (1998), pp. 69–94. · Zbl 0956.52014 |
| [9] | T. Chappell, T. Friedl, and R. Sanyal, Two double poset polytopes, SIAM J. Discrete Math., 31 (2017), pp. 2378–2413. · Zbl 1425.52011 |
| [10] | V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18 (1975), pp. 138–154. · Zbl 0277.05139 |
| [11] | V. Chvátal, Perfectly ordered graphs, in Topics on Perfect Graphs, C. Berge, V. Chvátal, eds., North-Holland Math. Stud. 88, Elsevier, Amsterdam, 1984, pp. 63–65. · Zbl 0559.05055 |
| [12] | M. Conforti, V. Kaibel, M. Walter, and S. Weltge, Subgraph polytopes and independence polytopes of count matroids, Oper. Res. Lett., 43 (2015), pp. 457–460. · Zbl 1408.90250 |
| [13] | R. Diestel, Graph Theory, Grad. Texts in Math, Springer, New York, 2005. · Zbl 1074.05001 |
| [14] | P. Eirinakis, D. Magos, I. Mourtos, and P. Miliotis, Polyhedral aspects of stable marriage, Math. Oper. Res., 39 (2013), pp. 656–671. · Zbl 1308.90107 |
| [15] | M. Escobar and Y. Faenza, Rotation-perfect stable marriage instances, manuscript, 2017. |
| [16] | S. Fiorini, V. Fisikopoulos, and M. Macchia, Two-level polytopes with a prescribed facet, in Combinatorial Optimization, R. Cerulli, S. Fujishige, and A. R. Mahjoub, eds., Springer, Cham, 2016, pp. 285–296. · Zbl 1397.52008 |
| [17] | D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962), pp. 9–15. · Zbl 0109.24403 |
| [18] | J. Gouveia, R. Grappe, V. Kaibel, K. Pashkovich, R. Z. Robinson, and R. Thomas, Which nonnegative matrices are slack matrices?, Linear Algebra Appl., 439 (2013), pp. 2921–2933. · Zbl 1283.15103 |
| [19] | J. Gouveia, M. Laurent, P. A. Parrilo, and R. Thomas, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program., 133 (2012), pp. 203–225. · Zbl 1262.90123 |
| [20] | J. Gouveia, P. A. Parrilo, and R. R. Thomas, Theta bodies for polynomial ideals, SIAM J. Optim., 20 (2010), pp. 2097–2118. · Zbl 1213.90190 |
| [21] | J. Gouveia, K. Pashkovich, R. Z. Robinson, and R. R. Thomas, Four-dimensional polytopes of minimum positive semidefinite rank, J. Comb. Theory Ser. A, 145 (2017), pp. 184–226. · Zbl 1360.52006 |
| [22] | J. Gouveia, R. Z. Robinson, and R. R. Thomas, Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50 (2013), pp. 679–699. · Zbl 1279.52023 |
| [23] | F. Grande and J. Rué, Many 2-level polytopes from matroids, Discrete Comput. Geom., 54 (2015), pp. 954–979. · Zbl 1342.05021 |
| [24] | F. Grande and R. Sanyal, Theta rank, levelness, and matroid minors, J. Combin. Theory Ser. B, 123 (2017), pp. 1–31. · Zbl 1354.05020 |
| [25] | J. L. Gross and J. Yellen, Graph Theory and Its Applications, CRC Press, Boca Raton, FL, 2005. · Zbl 1082.05001 |
| [26] | D. Gusfield, Three fast algorithms for four problems in stable marriage, SIAM J. Comput., 16 (1987), pp. 111–128. · Zbl 0635.68036 |
| [27] | D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, 1989. · Zbl 0703.68046 |
| [28] | O. Hanner, Intersections of translates of convex bodies, Math. Scand., 4 (1956), pp. 65–87. · Zbl 0070.39302 |
| [29] | A. B. Hansen, On a certain class of polytopes associated with independence systems, Math. Scand., 41 (1977), pp. 225–241. · Zbl 0411.05033 |
| [30] | T. Hibi and N. Li, Unimodular Equivalence of Order and Chain Polytopes, preprint, [math.Co], 2012. |
| [31] | R. W. Irving and P. Leather, The complexity of counting stable marriages, SIAM J. Comput., 15 (1986), pp. 655–667. · Zbl 0611.68015 |
| [32] | S. Iwata, N. Kamiyama, N. Katoh, S. Kijima, and Y. Okamoto, Extended formulations for sparsity matroids, Math. Program., 158 (2016), pp. 565–574. · Zbl 1343.05046 |
| [33] | V. Kaibel, J. Lee, M. Walter, and S. Weltge, Extended formulations for independence polytopes of regular matroids, Graphs Combin., 32 (2016), pp. 1931–1944. · Zbl 1354.05021 |
| [34] | G. Kalai, The number of faces of centrally-symmetric polytopes, Graphs Combin., 5 (1986), pp. 389–391. · Zbl 1168.52303 |
| [35] | D. E. Knuth, Mariages stables et leurs relations avec d’autres problèmes combinatoires: Introduction à l’analyse mathématique des algorithmes, Presses de l’Université de Montréal, Montréal, 1976. · Zbl 0358.68057 |
| [36] | U. H. Kortenkamp, J. Richter-Gebert, A. Sarangarajan, and G. M. Ziegler, Extremal properties of 0/1-polytopes, Discrete Comp. Geom., 17 (1997), pp. 439–448. · Zbl 0881.52005 |
| [37] | J. Lee, J. Leung, and F. Margot, Min-up/min-down polytopes, Discrete Optim., 1 (2004), pp. 77–85. · Zbl 1087.90053 |
| [38] | L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), pp. 253–267. · Zbl 0239.05111 |
| [39] | L. Lovász and M. E. Saks, Lattices, möbius functions and communication complexity, in Proceedings of the 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, 1988, IEEE Computer Society, pp. 81–90. |
| [40] | S. Lovett, Recent Advances on the Log-Rank Conjecture in Communication Complexity, [cs.CC], 2014. · Zbl 1409.68118 |
| [41] | R. K. Martin, Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett., 10 (1991), pp. 119–128. · Zbl 0747.90071 |
| [42] | J. G. Oxley, Matroid Theory, Oxford University Press, New York, 2006. · Zbl 1115.05001 |
| [43] | H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart., 20 (1982), pp. 16–21. · Zbl 0475.05046 |
| [44] | A. E. Roth, U. G. Rothblum, and J. H. V. Vate, Stable matchings, optimal assignments, and linear programming, Math. Oper. Res., 18 (1993), pp. 803–828. · Zbl 0806.90085 |
| [45] | T. Rothvoß, Some 0/1 polytopes need exponential size extended formulations, Math. Program., 142 (2013), pp. 255–268. · Zbl 1282.90245 |
| [46] | F. Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2), 176 (2012), pp. 383–412. · Zbl 1252.52007 |
| [47] | A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1998. · Zbl 0970.90052 |
| [48] | A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003. · Zbl 1041.90001 |
| [49] | P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory, Ser. B, 28 (1980), pp. 305–359. · Zbl 0443.05027 |
| [50] | R. P. Stanley, Two poset polytopes, Discrete Comput. Geom., 1 (1986), pp. 9–23. · Zbl 0595.52008 |
| [51] | S. Sullivant, Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. (2), 58 (2006), pp. 433–445. · Zbl 1121.52028 |
| [52] | S. Wagner and I. Gutman, Maxima and minima of the Hosoya index and the Merrifield-Simmons index, Acta Appl. Math., 112 (2010), pp. 323–346. · Zbl 1201.92068 |
| [53] | M. Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., 43 (1991), pp. 441–466. · Zbl 0748.90074 |
| [54] | G. M. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1995. · Zbl 0823.52002 |
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.
