Shifted simplicial complexes are Laplacian integral

Duval, Art; Reiner, Victor

doi:10.1090/S0002-9947-02-03082-9

Shifted simplicial complexes are Laplacian integral
HTML articles powered by AMS MathViewer

by Art M. Duval and Victor Reiner PDF

Trans. Amer. Math. Soc. 354 (2002), 4313-4344 Request permission

Abstract:

We show that the combinatorial Laplace operators associated to the boundary maps in a shifted simplicial complex have all integer spectra. We give a simple combinatorial interpretation for the spectra in terms of vertex degree sequences, generalizing a theorem of Merris for graphs. We also conjecture a majorization inequality for the spectra of these Laplace operators in an arbitrary simplicial complex, with equality achieved if and only if the complex is shifted. This generalizes a conjecture of Grone and Merris for graphs.

References

Ron M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), no. 3, 247–260. MR 1195888, DOI 10.1007/BF01285814
William N. Anderson Jr. and Thomas D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra 18 (1985), no. 2, 141–145. MR 817657, DOI 10.1080/03081088508817681
Anders Björner and Gil Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), no. 3-4, 279–303. MR 971798, DOI 10.1007/BF02392300
Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc. 348 (1996), no. 4, 1299–1327. MR 1333388, DOI 10.1090/S0002-9947-96-01534-6
Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945–3975. MR 1401765, DOI 10.1090/S0002-9947-97-01838-2
Fan R. K. Chung, The Laplacian of a hypergraph, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 21–36. MR 1235565
Fan R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. MR 1421568
Václav Chvátal and Peter L. Hammer, Aggregation of inequalities in integer programming, Studies in integer programming (Proc. Workshop, Bonn, 1975) Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam, 1977, pp. 145–162. MR 0479384
Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995. Theory and applications. MR 1324340
X. Dong and M. Wachs, Combinatorial Laplacian of the matching complex, Electron. J. Combin. 9 (2002), #R17, 11 pp.
P. Erdös and T. Grünwald, On polynomials with only real roots, Ann. of Math. (2) 40 (1939), 537–548. MR 7, DOI 10.2307/1968938
Isabel Faria, Multiplicity of integer roots of polynomials of graphs, Linear Algebra Appl. 229 (1995), 15–35. MR 1352837, DOI 10.1016/0024-3795(93)00337-Y
Miroslav Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), 298–305. MR 318007, DOI 10.21136/CMJ.1973.101168
Robin Forman, Combinatorial differential topology and geometry, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 177–206. MR 1731817
J. Friedman, Computing Betti numbers via combinatorial Laplacian, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, 1996), ACM, New York, 1996, pp. 386–391.
J. Friedman and P. Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), 193–203.
S. Gershgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 7 (1931), 749-754.
Robert D. Grone, Eigenvalues and the degree sequences of graphs, Linear and Multilinear Algebra 39 (1995), no. 1-2, 133–136. MR 1374475, DOI 10.1080/03081089508818384
Robert Grone and Russell Merris, The Laplacian spectrum of a graph. II, SIAM J. Discrete Math. 7 (1994), no. 2, 221–229. MR 1271994, DOI 10.1137/S0895480191222653
P. L. Hammer and A. K. Kelmans, Laplacian spectra and spanning trees of threshold graphs, Discrete Appl. Math. 65 (1996), no. 1-3, 255–273. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). MR 1380078, DOI 10.1016/0166-218X(94)00049-J
Gil Kalai, Enumeration of $\textbf {Q}$-acyclic simplicial complexes, Israel J. Math. 45 (1983), no. 4, 337–351. MR 720308, DOI 10.1007/BF02804017
G. Kirchhoff, Über de Auflösung der Gleichungen auf welche man bei der Untersuchen der linearen Vertheilung galvanischer Ströme gefüht wird, Ann. der Phys. und Chem. 72 (1847), 495-508.
W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc. 13 (2000), no. 1, 129–148. MR 1697094, DOI 10.1090/S0894-0347-99-00316-1
I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
Albert W. Marshall and Ingram Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, vol. 143, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 552278
Russell Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994), 381–389. MR 1274427, DOI 10.1016/0024-3795(94)90361-1
Russell Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994), 143–176. Second Conference of the International Linear Algebra Society (ILAS) (Lisbon, 1992). MR 1275613, DOI 10.1016/0024-3795(94)90486-3
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
Uri N. Peled and Murali K. Srinivasan, The polytope of degree sequences, Linear Algebra Appl. 114/115 (1989), 349–377. MR 986884, DOI 10.1016/0024-3795(89)90470-9
Ernst Ruch and Ivan Gutman, The branching extent of graphs, J. Combin. Inform. System Sci. 4 (1979), no. 4, 285–295. MR 573145
J. Stembridge, The MAPLE package posets, available at http://www.math.lsa.umich.edu/~jrs/maple.html#posets.