Combinatorial Laplacians of matroid complexes

Authors:
W. Kook, V. Reiner and D. Stanton

Journal:
J. Amer. Math. Soc. **13** (2000), 129-148

MSC (2000):
Primary 05B35

Published electronically:
September 13, 1999

MathSciNet review:
1697094

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**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**, 10.1017/CBO9780511662041.008**2.**Anders Björner and Gil Kalai,*On 𝑓-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**, 10.1111/j.1749-6632.1989.tb22438.x**3.**T. Brylawski,*Constructions*, in (ed. N. White), Encyclopedia of Mathematics and Its Applications,**26**, Cambridge Univ. Press, 1986. CMP**18:15****4.**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**, 10.1017/CBO9780511662041.007**5.**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**, 10.1016/S0012-365X(95)00332-Q**6.***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****7.**J. Friedman,*Computing Betti numbers via combinatorial Laplacians*, Algorithmica**21**(1998), no. 4, 331–346. MR**1622290**, 10.1007/PL00009218**8.**J. Friedman and P. Hanlon,*On the Betti numbers of chessboard complexes*, J. Algebraic Combin.**8**(1998), 193-203. CMP**99:02****9.**W. Kook,*Categories of acyclic graphs and automorphisms of free groups*, Ph.D. thesis (G. Carlsson, advisor), Stanford Univ., 1996.**10.**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****11.**Louis Solomon,*The Steinberg character of a finite group with 𝐵𝑁-pair*, Theory of Finite Groups (Symposium, Harvard Univ., Cambridge, Mass., 1968), Benjamin, New York, 1969, pp. 213–221. MR**0246951****12.**Richard P. Stanley,*Some aspects of groups acting on finite posets*, J. Combin. Theory Ser. A**32**(1982), no. 2, 132–161. MR**654618**, 10.1016/0097-3165(82)90017-6

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
05B35

Retrieve articles in all journals with MSC (2000): 05B35

Additional Information

**W. Kook**

Affiliation:
School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455

Address at time of publication:
Department of Mathematics, The George Washington University, Washington DC 20052

Email:
kook@math.umn.edu, andrewk@gwu.edu

**V. Reiner**

Affiliation:
School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455

Email:
reiner@math.umn.edu

**D. Stanton**

Affiliation:
School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455

Email:
stanton@math.umn.edu

DOI:
https://doi.org/10.1090/S0894-0347-99-00316-1

Keywords:
Matroid,
matroid complex,
Laplacian,
internal activity,
external activity

Received by editor(s):
July 16, 1997

Received by editor(s) in revised form:
June 30, 1999

Published electronically:
September 13, 1999

Additional Notes:
The second author was supported by Sloan Foundation and University of Minnesota McKnight Land Grant Fellowships. The third author was supported by NSF grant DMS-9400510.

Article copyright:
© Copyright 1999
American Mathematical Society