Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The Dehn-Sommerville relations and the Catalan matroid


Authors: Anastasia Chavez and Nicole Yamzon
Journal: Proc. Amer. Math. Soc. 145 (2017), 4041-4047
MSC (2010): Primary 52B05, 52B40
DOI: https://doi.org/10.1090/proc/13554
Published electronically: March 23, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Federico Ardila, The Catalan matroid, J. Combin. Theory Ser. A 104 (2003), no. 1, 49-62. MR 2018420, https://doi.org/10.1016/S0097-3165(03)00121-3
  • [2] 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, https://doi.org/10.1090/tran/6331
  • [3] 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, https://doi.org/10.1090/S0273-0979-1980-14712-6
  • [4] 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, https://doi.org/10.1016/0097-3165(81)90058-3
  • [5] 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, https://doi.org/10.1016/j.jcta.2008.07.004
  • [6] Anders Björner, The unimodality conjecture for convex polytopes, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 2, 187-188. MR 598684, https://doi.org/10.1090/S0273-0979-1981-14877-1
  • [7] 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
  • [8] 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, https://doi.org/10.1090/conm/178/01891
  • [9] Anders Björner, A comparison theorem for $ f$-vectors of simplicial polytopes, Pure Appl. Math. Q. 3 (2007), no. 1, 347-356. MR 2330164, https://doi.org/10.4310/PAMQ.2007.v3.n1.a12
  • [10] 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, https://doi.org/10.1016/S0097-3165(03)00122-5
  • [11] Ira Gessel and Gérard Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), no. 3, 300-321. MR 815360, https://doi.org/10.1016/0001-8708(85)90121-5
  • [12] Bernt Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90. MR 0335313, https://doi.org/10.1112/blms/5.1.85
  • [13] P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179-184. MR 0283691
  • [14] P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559-570. MR 0278183, https://doi.org/10.1007/BF02771471
  • [15] J. Oxley, Matroid Theory, 2nd ed., Oxford University Press Inc., 1992.
  • [16] B. Pawlowski, Catalan matroid decompositions of certain positroids, arXiv:1502.00158 [math.CO].
  • [17] A. Postnikov, Total positivity, Grassmannians, and networks, preprint. Available at http://www-math.mit.edu/$ \sim $apost/papers/tpgrass.pdf.
  • [18] Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236-238. MR 563925, https://doi.org/10.1016/0001-8708(80)90050-X
  • [19] Richard P. Stanley, Enumerative combinatorics. Vol. 2, with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. MR 1676282
  • [20] Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
  • [21] G. Ziegler, Lectures on Polytopes, 7th ed., Springer, 2006.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 52B05, 52B40

Retrieve articles in all journals with MSC (2010): 52B05, 52B40


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

DOI: https://doi.org/10.1090/proc/13554
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society