{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:57Z","timestamp":1787323377612,"version":"3.56.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>$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, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich, in Algorithms--ESA 2015, Springer, Berlin, 2015, pp. 191--202], and experimental results from [S. Fiorini, V. Fisikopoulos, and M. Macchia, in Combinatorial Optimization, Springer, Cham, 2016, pp. 285--296] 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.<\/jats:p>","DOI":"10.1137\/17m1116684","type":"journal-article","created":{"date-parts":[[2018,8,1]],"date-time":"2018-08-01T12:34:58Z","timestamp":1533126898000},"page":"1857-1886","source":"Crossref","is-referenced-by-count":17,"title":["On 2-Level Polytopes Arising in Combinatorial Settings"],"prefix":"10.1137","volume":"32","author":[{"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alfonso","family":"Cevallos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Faenza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,1]]},"reference":[{"key":"atypb1","first-page":"177","author":"Aprile M.","year":"2016","journal-title":"Switzerland"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Aprile, Y. Faenza, S. Fiorini, T. Huynh, and M. Macchia,\n                      Extension complexity of stable set polytopes of bipartite graphs\n                      , 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.","DOI":"10.1007\/978-3-319-68705-6_6"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90063-8"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/aima.2001.1991"},{"key":"atypb5","unstructured":"R. E. Bixby and W. H. Cunningham,\n                      Matroid Optimization and Algorithms\n                      , MIT Press, Cambridge, MA, 1996."},{"key":"atypb6","first-page":"191","author":"Bohn A.","year":"2015","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00225-2"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091800"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90041-6"},{"key":"atypb11","first-page":"63","author":"Chva\u0301tal V.","year":"1984","journal-title":"Amsterdam"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.06.011"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Grad. Texts in Math, Springer, New York, 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0616"},{"key":"atypb15","unstructured":"M. Escobar and Y. Faenza,\n                      Rotation-perfect stable marriage instances\n                      , manuscript, 2017."},{"key":"atypb16","first-page":"285","author":"Fiorini S.","year":"2016","journal-title":"Cham"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2013.08.009"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0425-z"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/090746525"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2016.08.002"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9533-x"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9735-5"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.11.002"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"J. L. Gross and J. Yellen,\n                      Graph Theory and Its Applications\n                      , CRC Press, Boca Raton, FL, 2005.","DOI":"10.1201\/9781420057140"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0216010"},{"key":"atypb27","unstructured":"D. Gusfield and R. W. Irving,\n                      The Stable Marriage Problem: Structure and Algorithms\n                      , MIT Press, Cambridge, MA, 1989."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10456"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-11716"},{"key":"atypb30","unstructured":"T. Hibi and N. Li,\n                      Unimodular Equivalence of Order and Chain Polytopes\n                      , preprint,arXiv:1208.4029[math.Co], 2012."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0936-8"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-016-1709-8"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788696"},{"key":"atypb35","unstructured":"D. E. Knuth,\n                      Mariages stables et leurs relations avec d'autres proble\u0300mes combinatoires: Introduction a\u0300 l'analyse mathe\u0301matique des algorithmes\n                      , Presses de l'Universite\u0301 de Montre\u0301al, Montre\u0301al, 1976."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009303"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2003.12.001"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90006-4"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"L. Lova\u0301sz and M. E. Saks,\n                      Lattices, mo\u0308bius functions and communication complexity\n                      , in Proceedings of the 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, 1988, IEEE Computer Society, pp. 81-90.","DOI":"10.1109\/SFCS.1988.21924"},{"key":"atypb40","unstructured":"S. Lovett,\n                      Recent Advances on the Log-Rank Conjecture in Communication Complexity\n                      ,arXiv:1403.8106[cs.CC], 2014."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90028-N"},{"key":"atypb42","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, New York, 2006."},{"key":"atypb43","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1080\/00150517.1982.12430021","volume":"20","author":"Prodinger H.","year":"1982","journal-title":"Fibonacci Quart."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.803"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"T. Rothvo\u00df,\n                      Some\n                      0\/1\n                      polytopes need exponential size extended formulations\n                      , Math. Program., 142 (2013), pp. 255-268.","DOI":"10.1007\/s10107-012-0574-3"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.1.7"},{"key":"atypb47","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , John Wiley & Sons, New York, 1998."},{"key":"atypb48","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer-Verlag, Berlin, 2003."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187680"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1163775139"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10440-010-9575-5"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"G. M. Ziegler,\n                      Lectures on Polytopes\n                      , Springer-Verlag, New York, 1995.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1116684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:48Z","timestamp":1787320728000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1116684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1116684"],"URL":"https:\/\/doi.org\/10.1137\/17m1116684","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}