DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

Font Size:  Small  Medium  Large

The Hodge Structure of the Coloring Complex of a Hypergraph (Extended Abstract)

Sarah C Rundell, Jane H Long

Abstract


Let G be a simple graph with n vertices. The coloring complex Δ(G) was defined by Steingrímsson, and the homology of Δ(G) was shown to be nonzero only in dimension n-3 by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group Hn-3(Δ(G)) where the dimension of the jth component in the decomposition, Hn-3(j)(Δ(G)), equals the absolute value of the coefficient of λj in the chromatic polynomial of G, χG(λ). Let H be a hypergraph with n vertices. In this paper, we define the coloring complex of a hypergraph, Δ(H), and show that the coefficient of λj in χH(λ) gives the Euler Characteristic of the jth Hodge subcomplex of the Hodge decomposition of Δ(H). We also examine conditions on a hypergraph, H, for which its Hodge subcomplexes are Cohen-Macaulay, and thus where the absolute value of the coefficient of λj in χH(λ) equals the dimension of the jth Hodge piece of the Hodge decomposition of Δ(H).
Résumé. Soit G un graphe simple à n sommets. Le complexe de coloriage Δ(G) a été défini par Steingrímsson et Jonsson a prouvé que l'homologie de Δ(G) est non nulle seulement en dimension n-3. Hanlon a récemment prouvé que les idempotents eulériens fournissent une décomposition du groupe d'homologie Hn-3(Δ(G)) où la dimension de la je composante dans la décomposition de Hn-3(j)(Δ(G)) est égale à la valeur absolue du coefficient de λj dans le polynôme chromatique de G, χG(λ) . Soit H un hypergraphe à n sommets. Dans ce texte, nous définissons le complexe de coloration d'un hypergraphe Δ(H) et nous prouvons que le coefficient de λj dans χH(λ) donne la caractéristique d'Euler du je sous-complexe de Hodge dans la décomposition de Hodge de Δ(H). Nous examinons également des conditions sur un hypergraphe H pour lesquelles les sous-complexes de Hodge sont Cohen-Macaulay. Ainsi la valeur absolue du coefficient de λj de χH(λ) est égale à la dimension du je sous-complexe de Hodge dans la décomposition de Hodge de Δ(H).

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional