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.
Additional Information
- Bruce E. Sagan
- Affiliation: Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027
- MR Author ID: 152890
- Email: sagan@math.msu.edu
- Received by editor(s): June 30, 1996
- Received by editor(s) in revised form: November 30, 1998
- Published electronically: February 16, 1999
- Additional Notes: Presented at the 35th meeting of the Séminaire Lotharingien de Combinatoire, October 4–6, 1995
- © Copyright 1999 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 36 (1999), 113-133
- MSC (1991): Primary 06A07; Secondary 05C15, 20F55, 06C10, 52B30
- DOI: https://doi.org/10.1090/S0273-0979-99-00775-2
- MathSciNet review: 1659875