Bulletin of the American Mathematical Society

Author(s): Bruce E. Sagan
Journal: Bull. Amer. Math. Soc. 36 (1999), 113-133.
MSC (1991): Primary 06A07; Secondary 05C15, 20F55, 06C10, 52B30
Posted: February 16, 1999
Retrieve article in: PDF DVI PostScript

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.

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 , 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 and , 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 , 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 , 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.

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

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

DOI: 10.1090/S0273-0979-99-00775-2
PII: S 0273-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, and in revised form November 30, 1998
Posted: February 16, 1999
Additional Notes: Presented at the 35th meeting of the Séminaire Lotharingien de Combinatoire, October 4--6, 1995
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS