The Dehn–Sommerville relations and the Catalan matroid
HTML articles powered by AMS MathViewer
- by Anastasia Chavez and Nicole Yamzon PDF
- Proc. Amer. Math. Soc. 145 (2017), 4041-4047 Request permission
Abstract:
The $f$-vector of a $d$-dimensional polytope $P$ stores the number of faces of each dimension. When $P$ is a simplicial polytope the Dehn–Sommerville relations condense the $f$-vector into the $g$-vector, which has length $\lceil {\frac {d+1}{2}}\rceil$. Thus, to determine the $f$-vector of $P$, we only need to know approximately half of its entries. This raises the question: Which $(\lceil {\frac {d+1}{2}}\rceil )$-subsets of the $f$-vector of a general simplicial polytope are sufficient to determine the whole $f$-vector? We prove that the answer is given by the bases of the Catalan matroid.References
- Federico Ardila, The Catalan matroid, J. Combin. Theory Ser. A 104 (2003), no. 1, 49–62. MR 2018420, DOI 10.1016/S0097-3165(03)00121-3
- Federico Ardila, Felipe Rincón, and Lauren Williams, Positroids and non-crossing partitions, Trans. Amer. Math. Soc. 368 (2016), no. 1, 337–363. MR 3413866, DOI 10.1090/tran/6331
- Louis J. Billera and Carl W. Lee, Sufficiency of McMullen’s conditions for $f$-vectors of simplicial polytopes, Bull. Amer. Math. Soc. (N.S.) 2 (1980), no. 1, 181–185. MR 551759, DOI 10.1090/S0273-0979-1980-14712-6
- Louis J. Billera and Carl W. Lee, A proof of the sufficiency of McMullen’s conditions for $f$-vectors of simplicial convex polytopes, J. Combin. Theory Ser. A 31 (1981), no. 3, 237–255. MR 635368, DOI 10.1016/0097-3165(81)90058-3
- Michael Björklund and Alexander Engström, The $g$-theorem matrices are totally nonnegative, J. Combin. Theory Ser. A 116 (2009), no. 3, 730–732. MR 2500168, DOI 10.1016/j.jcta.2008.07.004
- Anders Björner, The unimodality conjecture for convex polytopes, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 2, 187–188. MR 598684, DOI 10.1090/S0273-0979-1981-14877-1
- Anders Björner, Face numbers of complexes and polytopes, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 1408–1418. MR 934345, DOI 10.1007/bf02579197
- Anders Björner, Partial unimodality for $f$-vectors of simplicial polytopes and spheres, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 45–54. MR 1310573, DOI 10.1090/conm/178/01891
- Anders Björner, A comparison theorem for $f$-vectors of simplicial polytopes, Pure Appl. Math. Q. 3 (2007), no. 1, Special Issue: In honor of Robert D. MacPherson., 347–356. MR 2330164, DOI 10.4310/PAMQ.2007.v3.n1.a12
- Joseph Bonin, Anna de Mier, and Marc Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A 104 (2003), no. 1, 63–94. MR 2018421, DOI 10.1016/S0097-3165(03)00122-5
- Ira Gessel and Gérard Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), no. 3, 300–321. MR 815360, DOI 10.1016/0001-8708(85)90121-5
- Bernt Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90. MR 335313, DOI 10.1112/blms/5.1.85
- P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
- P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559–570. MR 278183, DOI 10.1007/BF02771471
- J. Oxley, Matroid Theory, 2nd ed., Oxford University Press Inc., 1992.
- B. Pawlowski, Catalan matroid decompositions of certain positroids, arXiv:1502.00158 [math.CO].
- A. Postnikov, Total positivity, Grassmannians, and networks, preprint. Available at http://www-math.mit.edu/$\sim$apost/papers/tpgrass.pdf.
- Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236–238. MR 563925, DOI 10.1016/0001-8708(80)90050-X
- Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
- Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
- G. Ziegler, Lectures on Polytopes, 7th ed., Springer, 2006.
Additional Information
- Anastasia Chavez
- Affiliation: Department of Mathematics, University of California, Berkeley, 970 Evans Hall 3840, Berkeley, California 94720
- Email: a.chavez@berkeley.edu
- Nicole Yamzon
- Affiliation: Department of Mathematics, San Francisco State University, 1600 Holloway Avenue, San Francisco, California 94132
- Email: nyamzon@mail.sfsu.edu
- Received by editor(s): December 26, 2015
- Received by editor(s) in revised form: August 18, 2016, and October 4, 2016
- Published electronically: March 23, 2017
- Additional Notes: The first author was supported in part by NSF Alliances for Graduate Education and the Professoriate
The second author was supported in part by NSF GK-12 grant DGE-0841164 - Communicated by: Patricia Hersh
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 4041-4047
- MSC (2010): Primary 52B05, 52B40
- DOI: https://doi.org/10.1090/proc/13554
- MathSciNet review: 3665055