Why the characteristic polynomial factors

Sagan, Bruce

doi:10.1090/S0273-0979-99-00775-2

Why the characteristic polynomial factors
HTML articles powered by AMS MathViewer

by Bruce E. Sagan PDF

Bull. Amer. Math. Soc. 36 (1999), 113-133 Request permission

Abstract:

We survey three methods for proving that the characteristic polynomial of a finite ranked lattice factors over the nonnegative integers and indicate how they have evolved recently. The first technique uses geometric ideas and is based on Zaslavsky’s theory of signed graphs. The second approach is algebraic and employs results of Saito and Terao about free hyperplane arrangements. Finally we consider a purely combinatorial theorem of Stanley about supersolvable lattices and its generalizations.

References

George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 0557013
Christos A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math. 122 (1996), no. 2, 193–233. MR 1409420, DOI 10.1006/aima.1996.0059
C. A. Athanasiadis and S. Linusson, A simple bijection for the regions of the Shi arrangement of hyperplanes, preprint.
Hélène Barcelo and Alain Goupil, Non-broken circuits of reflection groups and factorization in $D_n$, Israel J. Math. 91 (1995), no. 1-3, 285–306. MR 1348318, DOI 10.1007/BF02761652
Curtis Bennett and Bruce E. Sagan, A generalization of semimodular supersolvable lattices, J. Combin. Theory Ser. A 72 (1995), no. 2, 209–231. MR 1357770, DOI 10.1016/0097-3165(95)90061-6
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, Subspace arrangements, First European Congress of Mathematics, Vol. I (Paris, 1992) Progr. Math., vol. 119, Birkhäuser, Basel, 1994, pp. 321–370. MR 1341828
Anders Björner and Bruce E. Sagan, Subspace arrangements of type $B_n$ and $D_n$, J. Algebraic Combin. 5 (1996), no. 4, 291–314. MR 1406454, DOI 10.1023/A:1022492431260
A. Björner, L. Lovász and A. Yao, Linear decision trees: volume estimates and topological bounds, in “Proc. 24th ACM Symp. on Theory of Computing,” ACM Press, New York, NY, 1992, 170–177.
Anders Björner and Bruce E. Sagan, Subspace arrangements of type $B_n$ and $D_n$, J. Algebraic Combin. 5 (1996), no. 4, 291–314. MR 1406454, DOI 10.1023/A:1022492431260
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
Anders Björner and Volkmar Welker, The homology of “$k$-equal” manifolds and related partition lattices, Adv. Math. 110 (1995), no. 2, 277–313. MR 1317619, DOI 10.1006/aima.1995.1012
Andreas Blass and Bruce E. Sagan, Möbius functions of lattices, Adv. Math. 127 (1997), no. 1, 94–123. MR 1445364, DOI 10.1006/aima.1997.1616
A. Blass and B. E. Sagan, Characteristic and Ehrhart polynomials, J. Algebraic Combin. 7 (1998), 115–126.
K. Bogart, The Möbius function of the domination lattice, unpublished manuscript, 1972.
Thomas Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201–219. MR 325405, DOI 10.1016/0012-365X(73)90094-0
T. Brylawski, The broken circuit complex, Trans. Amer. Math. Soc. 234 (1977), 417–433.
Gary Chartrand and Linda Lesniak, Graphs and digraphs, 2nd ed., The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. MR 834583
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
Paul H. Edelman and Victor Reiner, Free hyperplane arrangements between $A_{n-1}$ and $B_n$, Math. Z. 215 (1994), no. 3, 347–365. MR 1262522, DOI 10.1007/BF02571719
Haya Friedman and Dov Tamari, Erratum to: “Problèmes d’associativité: Une structure de treillis finis induite par une loi demi-associative”, J. Combinatorial Theory 4 (1968), 201 (French). MR 238985, DOI 10.1007/bf00275986
George Grätzer, Lattice theory. First concepts and distributive lattices, W. H. Freeman and Co., San Francisco, Calif., 1971. MR 0321817
Curtis Greene, A class of lattices with Möbius function $\pm 1,0$, European J. Combin. 9 (1988), no. 3, 225–240. MR 947024, DOI 10.1016/S0195-6698(88)80013-1
Curtis Greene, Posets of shuffles, J. Combin. Theory Ser. A 47 (1988), no. 2, 191–206. MR 930953, DOI 10.1016/0097-3165(88)90018-0
Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), no. 1, 17–76. MR 1256101, DOI 10.1023/A:1022450120589
P. Headley, “Reduced Expressions in Infinite Coxeter Groups,” Ph.D. thesis, University of Michigan, Ann Arbor, 1994.
P. Headley, On reduced words in affine Weyl groups, in “Formal Power Series and Algebraic Combinatorics, May 23–27, 1994,” DIMACS, Rutgers, 1994, 225–242.
Samuel Huang and Dov Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combinatorial Theory Ser. A 13 (1972), 7–13. MR 306064, DOI 10.1016/0097-3165(72)90003-9
James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
Michel Jambu and Luis Paris, Combinatorics of inductively factored arrangements, European J. Combin. 16 (1995), no. 3, 267–292. MR 1330542, DOI 10.1016/0195-6698(95)90032-2
Tadeusz Józefiak and Bruce E. Sagan, Basic derivations for subarrangements of Coxeter arrangements, J. Algebraic Combin. 2 (1993), no. 3, 291–320. MR 1235282, DOI 10.1023/A:1022455716471
G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
S. Linusson, Möbius functions and characteristic polynomials for subspace arrangements embedded in $B_n$, preprint.
Svante Linusson, Partitions with restricted block sizes, Möbius functions, and the $k$-of-each problem, SIAM J. Discrete Math. 10 (1997), no. 1, 18–29. MR 1430543, DOI 10.1137/S089548019426855X
Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
A. Postnikov, “Enumeration in algebra and geometry,” Ph.D. thesis, M.I.T., Cambridge, 1997.
A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, preprint.
V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195–222.
Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). MR 174487, DOI 10.1007/BF00531932
Kyoji Saito, Theory of logarithmic differential forms and logarithmic vector fields, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 27 (1980), no. 2, 265–291. MR 586450
Jian Yi Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Mathematics, vol. 1179, Springer-Verlag, Berlin, 1986. MR 835214, DOI 10.1007/BFb0074968
Jian Yi Shi, Alcoves corresponding to an affine Weyl group, J. London Math. Soc. (2) 35 (1987), no. 1, 42–55. MR 871764, DOI 10.1112/jlms/s2-35.1.42
R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–217. MR 309815, DOI 10.1007/BF02945028
Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
Richard P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 6, 2620–2625. MR 1379568, DOI 10.1073/pnas.93.6.2620
Sheila Sundaram, Applications of the Hopf trace formula to computing homology representations, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 277–309. MR 1310588, DOI 10.1090/conm/178/01904
Sheila Sundaram and Michelle Wachs, The homology representations of the $k$-equal partition lattice, Trans. Amer. Math. Soc. 349 (1997), no. 3, 935–954. MR 1389790, DOI 10.1090/S0002-9947-97-01806-0
Sheila Sundaram and Volkmar Welker, Group actions on arrangements of linear subspaces and applications to configuration spaces, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1389–1420. MR 1340186, DOI 10.1090/S0002-9947-97-01565-1
Hiroaki Terao, Arrangements of hyperplanes and their freeness. I, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 27 (1980), no. 2, 293–312. MR 586451
Hiroaki Terao, Free arrangements of hyperplanes and unitary reflection groups, Proc. Japan Acad. Ser. A Math. Sci. 56 (1980), no. 8, 389–392. MR 596011
Hiroaki Terao, Free arrangements of hyperplanes over an arbitrary field, Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 7, 301–303. MR 726186
Hiroaki Terao, The Jacobians and the discriminants of finite reflection groups, Tohoku Math. J. (2) 41 (1989), no. 2, 237–247. MR 996012, DOI 10.2748/tmj/1178227822
Hiroaki Terao, The Jacobians and the discriminants of finite reflection groups, Tohoku Math. J. (2) 41 (1989), no. 2, 237–247. MR 996012, DOI 10.2748/tmj/1178227822
Herbert S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., Boston, MA, 1994. MR 1277813
Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. 1 (1975), no. issue 1, 154, vii+102. MR 357135, DOI 10.1090/memo/0154
Thomas Zaslavsky, The geometry of root systems and signed graphs, Amer. Math. Monthly 88 (1981), no. 2, 88–105. MR 606249, DOI 10.2307/2321133
Thomas Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982), no. 2, 215–228. MR 675866, DOI 10.1016/0012-365X(82)90144-3
Thomas Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982), no. 2, 215–228. MR 675866, DOI 10.1016/0012-365X(82)90144-3
G. Ziegler, Algebraic combinatorics of hyperplane arrangements, Ph. D. thesis, M.I.T., Cambridge, MA, 1987.