Hypergraph coloring complexes

DOI10.1016/J.DISC.2012.04.027MaRDI QIDQ442337zbMATH OpenOpenAlexWikidataFDO

Authors Felix Breuer, Aaron Dall, Martina Kubitzke

Publication date 10 August 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1104.0483

zbMATH Keywords

chromatic polynomialCohencoloring complexEhrhart theoryhypergraphMacaulaywedge lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Cohen-Macaulay modules (13C14)

Abstract: The aim of this paper is to generalize the notion of the coloring complex of a graph to hypergraphs. We present three different interpretations of those complexes -- a purely combinatorial one and two geometric ones. It is shown, that most of the properties, which are known to be true for coloring complexes of graphs, break down in this more general setting, e.g., Cohen-Macaulayness and partitionabilty. Nevertheless, we are able to provide bounds for the $f$- and $h$-vectors of those complexes which yield new bounds on chromatic polynomials of hypergraphs. Moreover, it is shown that the coloring complex of a hypergraph has a wedge decomposition, though we conjecture that in general this decomposition is not homotopy equivalent to a wedge of spheres. In addition, we can completely characterize those hypergraphs whose coloring complex is connected.

Recommendations

• The Hodge structure of the coloring complex of a hypergraph (extended abstract)
• The Hodge structure of the coloring complex of a hypergraph
• Hom complexes and hypergraph colorings
• The topology of the coloring complex
• The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph

Cites work

• A Hodge decomposition interpretation for the coefficients of the chromatic polynomial
• Coloring complexes and arrangements
• Combinatorics and commutative algebra.
• Complexes of graph homomorphisms
• Computing the Continuous Discretely
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• Homotopy types of subspace arrangements via diagrams of spaces
• scientific article; zbMATH DE number 1194481 (Why is no real title available?)
• scientific article; zbMATH DE number 3547324 (Why is no real title available?)
• scientific article; zbMATH DE number 409491 (Why is no real title available?)
• Inside-out polytopes
• Kneser's conjecture, chromatic number, and homotopy
• Lectures on Polytopes
• Link complexes of subspace arrangements
• Proof of the Lovász conjecture
• The coloring ideal and coloring complex of a graph
• The Hodge structure of the coloring complex of a hypergraph
• The Koszul property in affine semigroup rings
• The number of nowhere-zero flows on graphs and signed graphs
• The topology of the coloring complex
• Viewing counting polynomials as Hilbert functions via Ehrhart theory

Cited in

(12)

• The topology of the coloring complex
• Pruned inside-out polytopes, combinatorial reciprocity theorems and generalized permutahedra
• On Cohen-Macaulay Hopf monoids in species
• Coloring complexes and arrangements
• scientific article; zbMATH DE number 4033788 (Why is no real title available?)
• Hom complexes and hypergraph colorings
• Hyperoctahedral Eulerian idempotents, Hodge decompositions, and signed graph coloring complexes
• The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph
• The Hodge structure of the coloring complex of a hypergraph (extended abstract)
• Homotopy and Hom construction in the category of finite hypergraphs
• The Hodge structure of the coloring complex of a hypergraph
• Scheduling problems

Describes a project that uses

Uses Software

• SageMath
• OEIS

This page was built for publication: Hypergraph coloring complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442337)