Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Why the characteristic polynomial factors


Author: Bruce E. Sagan
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
Published electronically: February 16, 1999
MathSciNet review: 1659875
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. G. Andrews, ``The Theory of Partitions,'' Addison-Wesley, Reading, MA, 1976. MR 58:27738
  • 2. C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. in Math. 122 (1966), 193-233. MR 97k:52012
  • 3. C. A. Athanasiadis and S. Linusson, A simple bijection for the regions of the Shi arrangement of hyperplanes, preprint.
  • 4. H. Barcelo and A. Goupil, Non-broken circuits of reflection groups and their factorization in $D_n$, Israel J. Math. 91 (1995), 285-306. MR 96g:20058
  • 5. C. Bennett and B. E. Sagan, A generalization of semimodular supersolvable lattices, J. Algebraic Combin. 72 (1995), 209-231. MR 96i:05180
  • 6. A. Björner, The homology and shellability of matroids and geometric lattices, Chapter 7 in ``Matroid Applications,'' N. White ed., Cambridge University Press, Cambridge, 1992, 226-283. MR 94a:52030
  • 7. A. Björner, Subspace arrangements, in ``Proc. 1st European Congress Math. (Paris 1992),'' A. Joseph and R. Rentschler eds., Progress in Math., Vol. 122, Birkhäuser, Boston, MA, (1994), 321-370. MR 96h:52012
  • 8. A. Björner and L. Lovász, Linear decision trees, subspace arrangements and Möbius functions, J. Amer. Math. Soc. 7 (1994), 667-706. MR 97g:52028
  • 9. 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.
  • 10. A. Björner and B. Sagan, Subspace arrangements of type $B_n$ and $D_n$, J. Algebraic Combin., 5 (1996), 291-314. MR 97g:52028
  • 11. A. Björner and M. Wachs, Nonpure shellable complexes and posets I, Trans. Amer. Math. Soc. 348 (1996), 1299-1327. MR 96i:06008
  • 12. A. Björner and M. Wachs, Nonpure shellable complexes and posets II, Trans. Amer. Math. Soc. 349 (1997), 3945-3975. MR 98b:06008
  • 13. A. Björner and V. Welker, The homology of ``$k$-equal'' manifolds and related partition lattices, Adv. in Math. 110 (1995), 277-313. MR 95m:52029
  • 14. A. Blass and B. E. Sagan, Möbius functions of lattices, Adv. in Math. 127 (1997), 94-123. MR 98c:06001
  • 15. A. Blass and B. E. Sagan, Characteristic and Ehrhart polynomials, J. Algebraic Combin. 7 (1998), 115-126. CMP 98:10
  • 16. K. Bogart, The Möbius function of the domination lattice, unpublished manuscript, 1972.
  • 17. T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201-219. MR 48:3752
  • 18. T. Brylawski, The broken circuit complex, Trans. Amer. Math. Soc. 234 (1977), 417-433.
  • 19. G. Chartrand and L. Lesniak, ``Graphs and Digraphs,'' second edition, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986. MR 87h:05001
  • 20. H. Crapo and G.-C. Rota, ``On the Foundations of Combinatorial Theory: Combinatorial Geometries,'' M.I.T. Press, Cambridge, MA, 1970. MR 45:74
  • 21. P. H. Edelman and V. Reiner, Free hyperplane arrangements between $A_{n-1}$ and $B_n$, Math. Zeitschrift 215 (1994), 347-365. MR 95b:52021
  • 22. H. Friedman and D. Tamari, Problèmes d'associativité: Une treillis finis induite par une loi demi-associative, J. Combin. Theory 2 (1967), 215-242. MR 39:345;MR 39:344
  • 23. G. Grätzer, ``Lattice Theory,'' Freeman and Co., San Francisco, CA, 1971, pp. 17-18, problems 26-36. MR 48:184
  • 24. C. Greene, A class of lattices with Möbius function $\pm 1,0$, European J. Combin. 9 (1988), 225-240. MR 89i:06012
  • 25. C. Greene, Posets of Shuffles, J. Combin. Theory Ser. A 47 (1988), 191-206. MR 89d:06003
  • 26. M. Haiman, Conjectures on the quotient ring of diagonal invariants. J. Alg. Combin. , 3 (1994), 17-76. MR 95a:20014
  • 27. P. Headley, ``Reduced Expressions in Infinite Coxeter Groups,'' Ph.D. thesis, University of Michigan, Ann Arbor, 1994.
  • 28. 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.
  • 29. S. Huang and D. Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combin. Theory Ser. A 13 (1972), 7-13. MR 46:5191
  • 30. J. E. Humphreys, ``Reflection Groups and Coxeter Groups,'' Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1990. MR 92h:20002
  • 31. M. Jambu and L. Paris, Combinatorics of inductively factored arrangements, European J. Combin. 16 (1995), 267-292. MR 96c:52022
  • 32. T. Józefiak and B. E. Sagan, Basic derivations for subarrangements of Coxeter arrangements, J. Algebraic Combin. 2 (1993), 291-320. MR 94j:52023
  • 33. G. Kreweras, Sur les partitions non-croisées d'un cycle, Discrete Math. 1 (1972), 333-350. MR 46:8852
  • 34. S. Linusson, Möbius functions and characteristic polynomials for subspace arrangements embedded in $B_n$, preprint.
  • 35. S. Linusson, Partitions with restricted block sizes, Möbius functions and the $k$-of-each problem, SIAM J. Discrete Math. 10 (1997), 18-29. MR 97i:68095
  • 36. P. Orlik and H. Terao, ``Arrangements of Hyperplanes,'' Grundlehren 300, Springer-Verlag, New York, NY, 1992. MR 94e:52014
  • 37. A. Postnikov, ``Enumeration in algebra and geometry,'' Ph.D. thesis, M.I.T., Cambridge, 1997.
  • 38. A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, preprint.
  • 39. V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195-222. CMP 98:05
  • 40. G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340-368. MR 30:4688
  • 41. K. Saito, Theory of logarithmic differential forms and logarithmic vector fields, J. Fac. Sci. Univ. Tokyo Sec. 1A Math. 27 (1980), 265-291. MR 83h:32023
  • 42. J. Y. Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Math., Vol. 1179, Springer-Verlag, New York, NY, 1986. MR 87i:20074
  • 43. J. Y. Shi, Sign types corresponding to an affine Weyl group, J. London Math. Soc. 35 (1987), 56-74. MR 88g:20103b
  • 44. R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197-217. MR 46:8920
  • 45. R. P. Stanley, ``Enumerative Combinatorics, Volume 1,'' Cambridge University Press, Cambridge, 1997. MR 98a:05001
  • 46. R. P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Nat. Acad. Sci. 93 (1996) 2620-2625. MR 97i:52013
  • 47. S. Sundaram, Applications of the Hopf trace formula to computing homology representations, Contemp. Math. 178 (1994), 277-309. MR 96f:05193
  • 48. S. Sundaram and M. Wachs, The homology representations of the $k$-equal partition lattice, Trans. Amer. Math. Soc. 349 (1997) 935-954. MR 97j:05063
  • 49. S. Sundaram and V. Welker, Group actions on arrangements of linear subspaces and applications to configuration spaces, Trans. Amer. Math. Soc. 349 (1997) 1389-1420. MR 97h:52012
  • 50. H. Terao, Arrangements of hyperplanes and their freeness I, II, J. Fac. Sci. Univ. Tokyo, 27 (1980), 293-320. MR 84i:32016a; MR 84i:32016b
  • 51. H. Terao, Generalized exponents of a free arrangement of hyperplanes and the Shepherd-Todd-Brieskorn formula, Invent. Math. 63 (1981), 159-179. MR 82e:32018b
  • 52. H. Terao, Free arrangements of hyperplanes over an arbitrary field, Proc. Japan Acad. Ser. A Math 59 (1983), 301-303. MR 85f:32017
  • 53. H. Terao, The Jacobians and the discriminants of finite reflection groups, Tôhoku Math. J. 41 (1989), 237-247. MR 90m:32028
  • 54. H. Terao, Factorizations of Orlik-Solomon algebras, Adv. in Math. 91 (1992), 45-53. MR 90m:32028
  • 55. H. S. Wilf, ``Generatingfunctionology,'' Academic Press, Boston, MA, 1990. MR 95a:05002
  • 56. T. Zaslavsky, ``Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes,'' Memoirs Amer. Math. Soc., No. 154, Amer. Math. Soc., Providence, RI, 1975. MR 50:9603
  • 57. T. Zaslavsky, The geometry of root systems and signed graphs, Amer. Math. Monthly 88 (1981), 88-105. MR 82g:05012
  • 58. T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982) 215-228. MR 84h:05050a
  • 59. T. Zaslavsky, Chromatic invariants of signed graphs, Discrete Math. 42 (1982) 287-312. MR 84h:05050b
  • 60. G. Ziegler, Algebraic combinatorics of hyperplane arrangements, Ph. D. thesis, M.I.T., Cambridge, MA, 1987.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1991): 06A07, 05C15, 20F55, 06C10, 52B30

Retrieve articles in all journals with MSC (1991): 06A07, 05C15, 20F55, 06C10, 52B30


Additional Information

Bruce E. Sagan
Affiliation: Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027
Email: sagan@math.msu.edu

DOI: https://doi.org/10.1090/S0273-0979-99-00775-2
Keywords: Characteristic polynomial, free arrangement, M\"obius function, partially ordered set, signed graph, subspace arrangement, supersolvable lattice
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
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society