Combinatorial Laplacians of matroid complexes

Kook, W.; Reiner, V.; Stanton, D.

doi:10.1090/S0894-0347-99-00316-1

Combinatorial Laplacians of matroid complexes
HTML articles powered by AMS MathViewer

by W. Kook, V. Reiner and D. Stanton PDF

J. Amer. Math. Soc. 13 (2000), 129-148 Request permission

Abstract:

We combinatorially interpret the spectra of discrete Laplace operators from the boundary maps in the simplicial complex of independent sets of a matroid. The interpretation follows from a surprising orthogonal decomposition of the simplicial chain groups. This decomposition is in general finer than the spectral decomposition. As a consequence, the spectra are integral. One corollary to our combinatorial interpretation may be paraphrased as stating that one can “hear" the characteristic polynomial of a matroid.

References

Anders Björner, The homology and shellability of matroids and geometric lattices, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226–283. MR 1165544, DOI 10.1017/CBO9780511662041.008
Anders Björner and Gil Kalai, On $f$-vectors and homology, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 63–80. MR 1018610, DOI 10.1111/j.1749-6632.1989.tb22438.x
T. Brylawski, Constructions, in Theory of Matroids (ed. N. White), Encyclopedia of Mathematics and Its Applications, 26, Cambridge Univ. Press, 1986.
Thomas Brylawski and James Oxley, The Tutte polynomial and its applications, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225. MR 1165543, DOI 10.1017/CBO9780511662041.007
Gwihen Etienne and Michel Las Vergnas, External and internal elements of a matroid basis, Discrete Math. 179 (1998), no. 1-3, 111–119. MR 1489076, DOI 10.1016/S0012-365X(95)00332-Q
Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 1996. Held in Philadelphia, PA, May 22–24, 1996. MR 1427491
J. Friedman, Computing Betti numbers via combinatorial Laplacians, Algorithmica 21 (1998), no. 4, 331–346. MR 1622290, DOI 10.1007/PL00009218
J. Friedman and P. Hanlon, On the Betti numbers of chessboard complexes, J. Algebraic Combin. 8 (1998), 193–203.
W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford Univ., 1996.
Bruce E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Representations, combinatorial algorithms, and symmetric functions. MR 1093239
Louis Solomon, The Steinberg character of a finite group with $BN$-pair, Theory of Finite Groups (Symposium, Harvard Univ., Cambridge, Mass., 1968) Benjamin, New York, 1969, pp. 213–221. MR 0246951
Richard P. Stanley, Some aspects of groups acting on finite posets, J. Combin. Theory Ser. A 32 (1982), no. 2, 132–161. MR 654618, DOI 10.1016/0097-3165(82)90017-6