×

zbMATH — the first resource for mathematics

\( h\)-vectors of matroids and logarithmic concavity. (English) Zbl 1304.05013
Summary: Let \( M\) be a matroid on \( E\), representable over a field of characteristic zero. We show that \( h\)-vectors of the following simplicial complexes are log-concave: (1) The matroid complex of independent subsets of \( E\). (2) The broken circuit complex of \( M\) relative to an ordering of \( E\).
The first implies a conjecture of Colbourn on the reliability polynomial of a graph, and the second implies a conjecture of Hoggar on the chromatic polynomial of a graph. The proof is based on the geometric formula for the characteristic polynomial of Denham, Garrousian, and Schulze.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aigner, M., Whitney numbers, (Combinatorial Geometries, Encyclopedia Math. Appl., vol. 29, (1987), Cambridge University Press Cambridge), 139-160
[2] Billera, L.; Lee, C., A proof of the sufficiency of Mcmullen’s conditions for f-vectors of simplicial convex polytopes, J. Combin. Theory Ser. A, 31, 237-255, (1981) · Zbl 0479.52006
[3] Björner, A., The unimodality conjecture for convex polytopes, Bull. Amer. Math. Soc., 4, 187-188, (1981) · Zbl 0458.52004
[4] Björner, A., The homology and shellability of matroids and geometric lattices, (Matroid Applications, Encyclopedia Math. Appl., vol. 40, (1992), Cambridge University Press Cambridge), 226-283 · Zbl 0772.05027
[5] Brenti, F., Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, (Jerusalem Combinatorics ’93, Contemp. Math., vol. 178, (1994), American Mathematical Society Providence), 71-89 · Zbl 0813.05007
[6] Brown, J.; Colbourn, C., On the log concavity of reliability and matroidal sequences, Adv. in Appl. Math., 15, 114-127, (1994) · Zbl 0802.05024
[7] Brylawski, T., The broken-circuit complex, Trans. Amer. Math. Soc., 234, 417-433, (1977) · Zbl 0368.05022
[8] Brylawski, T., Constructions, (Theory of Matroids, Encyclopedia Math. Appl., vol. 26, (1986), Cambridge University Press Cambridge), 127-223
[9] Cohen, D.; Denham, G.; Falk, M.; Varchenko, A., Critical points and resonance of hyperplane arrangements, Canad. J. Math., 63, 1038-1057, (2011) · Zbl 1228.32028
[10] Colbourn, C., The combinatorics of network reliability, Int. Ser. Monogr. Comput. Sci., (1987), The Clarendon Press, Oxford University Press New York
[11] Dawson, J., A collection of sets related to the Tutte polynomial of a matroid, (Graph Theory, Singapore, 1983, Lecture Notes in Math., vol. 1073, (1984), Springer Berlin), 193-204
[12] De Loera, J.; Kemper, Y.; Klee, S., h-vectors of small matroid complexes, Electron. J. Combin., 19, (2012), Paper 14, 11 pp · Zbl 1244.05238
[13] Denham, G.; Garrousian, M.; Schulze, M., A geometric deletion-restriction formula, Adv. Math., 230, 1979-1994, (2012) · Zbl 1317.52032
[14] Hartshorne, R., Varieties of small codimension in projective space, Bull. Amer. Math. Soc., 80, 1017-1032, (1974) · Zbl 0304.14005
[15] Hoggar, S., Chromatic polynomials and logarithmic concavity, J. Combin. Theory Ser. B, 16, 248-254, (1974) · Zbl 0268.05104
[16] Huh, J., Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc., 25, 907-927, (2012) · Zbl 1243.14005
[17] Huh, J., The maximum likelihood degree of a very affine variety, Compos. Math., 149, 1245-1266, (2013) · Zbl 1282.14007
[18] Huh, J.; Katz, E., Log-concavity of characteristic polynomials and the Bergman Fan of matroids, Math. Ann., 354, 3, 1103-1116, (2012) · Zbl 1258.05021
[19] Lenz, M., The f-vector of a representable-matroid complex is log-concave, Adv. in Appl. Math., 51, 543-545, (2013) · Zbl 1301.05382
[20] Lenz, M., Matroids and log-concavity, (2013)
[21] Lundow, P. H.; Markström, K., Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials, Experiment. Math., 15, 343-353, (2006) · Zbl 1120.05032
[22] Marker, D., Model theory. an introduction, Grad. Texts in Math., vol. 217, (2002), Springer-Verlag New York · Zbl 1003.03034
[23] Mason, J., Matroids: unimodal conjectures and Motzkin’s theorem, (Combinatorics, Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972, (1972), Inst. Math. Appl. Southend-on-Sea), 207-220
[24] Miller, E.; Sturmfels, B., Combinatorial commutative algebra, Grad. Texts in Math., vol. 227, (2005), Springer-Verlag New York · Zbl 1090.13001
[25] Orlik, P.; Terao, H., Arrangements of hyperplanes, Grundlehren Math. Wiss., vol. 300, (1992), Springer-Verlag Berlin · Zbl 0757.55001
[26] Orlik, P.; Terao, H., The number of critical points of a product of powers of linear functions, Invent. Math., 120, 1-14, (1995) · Zbl 0934.32020
[27] Oxley, J., Matroid theory, Oxf. Grad. Texts Math., vol. 21, (2011), Oxford University Press Oxford · Zbl 1254.05002
[28] Stanley, R., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph Theory and Its Applications: East and West, Jinan, 1986, Ann. New York Acad. Sci., 576, 500-535, (1989) · Zbl 0792.05008
[29] Stanley, R., Positivity problems and conjectures in algebraic combinatorics, (Mathematics: Frontiers and Perspectives, (2000), American Mathematical Society Providence), 295-319 · Zbl 0955.05111
[30] Varchenko, A., Critical points of the product of powers of linear functions and families of bases of singular vectors, Compos. Math., 97, 385-401, (1995) · Zbl 0842.17044
[31] Wagner, D., Negatively correlated random variables and Mason’s conjecture for independent sets in matroids, Ann. Comb., 12, 211-239, (2008) · Zbl 1145.05003
[32] Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc., 38, 572-579, (1932) · JFM 58.0605.08
[33] Wilf, H., Which polynomials are chromatic?, (Colloquio Internazionale sulle Teorie Combinatorie, Tomo I, Roma, 1973, Atti Conv. Lincei, vol. 17, (1976), Accademia Nazionale dei Lincei Rome), 247-256
[34] Zaslavsky, T., The Möbius function and the characteristic polynomial, (Combinatorial Geometries, Encyclopedia Math. Appl., vol. 29, (1987), Cambridge University Press Cambridge), 114-138
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.