<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 1" %>
A Factorization Theorem of Characteristic Polynomials of Convex Geometries
M. Hachimori1, M. Nakamura2
1Graduate School of Systems and Information Sciences, University of Tsukuba, Tsukuba, Ibaraki, Japan
2Department of Systems Science, College of Arts and Sciences, University of Tokyo, Komaba 3-8, Meguro, Tokyo, Japan
nakamura@klee.c.u-tokyo.ac.jp
Annals of Combinatorics 11 (1) p.39-46 March, 2007
AMS Subject Classification: 05A99
Abstract:
A convex geometry is a closure system whose closure operator satisfies the antiexchange property. As is described in Sagan's survey paper, characteristic polynomials factorize over nonnegative integers in several situations. We show that the characteristic polynomial of a 2-tight convex geometry K factorizes over nonnegative integers if the clique complex of the nbc-graph of K is pure and strongly connected. This factorization theorem is new in the sense that it does not belong to any of the three categories mentioned in Sagan's survey.
Keywords: closure system, broken circuit, NBC complex, strongly connected, chordal graph

References:

1. C. Bennett and B.E. Sagan, A generalization of semimodular supersolvable lattices, J. Combin. Theory Ser. A 72 (1995) 209-231.

2. A. Björner, The homology and shellability of matroids and geometric lattices, In: Matroid Applications, N. White Ed., Cambridge University Press, (1992) pp. 226-283.

3. A. Börner, Topological methods, In: Handbook of Combinatorics, Vol. 2, G.L. Graham et al. Eds., Elsevier, (1995) pp. 1819-1872.

4. A. Björner and G.M. Ziegler, Broken circuit complexes: factorizations and generalizations, J. Combin. Theory Ser. B 51 (1) (1991) 96-126.

5. P.H. Edelman, Abstract convexity and meet-distributive lattices, Contemp. Math. 57 (1986) 127-150.

6. K. Kashiwabara and M. Nakamura, On the NBC complexes and the Orlik-Solomon type algebras, preprint.

7. B. Korte, L. Lovász, and R. Schrader, Greedoids, Algorithms and Combinatorics 4, Springer- Verlag, 1991.

8. P.O. Orlik and H. Terao, Arrangments of Hyperplanes, Grundlehren der Mathematischen Wissenschaften, Vol. 300, Springer-Verlag, Berlin, 1992.

9. B.E. Sagan, Why the characteristic polynomial factors, Bull. Amer. Math. Soc. (N.S.) 38 (1999) 113-133.

10. K. Saito, Theory of logarithmic differential forms and logarithmic vector fields, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 27 (1980) 215-291.

11. R.P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972) 197-217.

12. H. Terao, Generalized exponents of a free arrangement of hyperplanes and the Shephered- Todd-Briekson formula, Invent. Math. 63 (1981) 159-179.

13. T. Zaslavsky, The geometry of rooted systems, and signed graphs, Amer. Math. Monthly 88 (2) (1981) 88-105.

14. T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982) 215-228.

15. T. Zaslavsky, Chromatic invariants of signed graphs, Discrete Math. 42 (1982) 287-312.

16. G.M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.