On generalized Kneser hypergraph colorings

DOI10.1016/J.JCTA.2006.02.003MaRDI QIDQ857422zbMATH OpenOpenAlexFDO

Authors Carsten E. M. C. Lange, Günter M. Ziegler

Publication date 14 December 2006

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

colorings of hypergraphsintersection multiplicities

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In Ziegler (2002), the second author presented a lower bound for the chromatic numbers of hypergraphs $KGrpmbscalS$, "generalized $r$-uniform Kneser hypergraphs with intersection multiplicities $pmbs$." It generalized previous lower bounds by Kriz (1992/2000) for the case $pmbs=(1,\mathrm{...},1)$ without intersection multiplicities, and by Sarkaria (1990) for $calS=binom[n]k$. Here we discuss subtleties and difficulties that arise for intersection multiplicities $s_i>1$: 1. In the presence of intersection multiplicities, there are two different versions of a "Kneser hypergraph," depending on whether one admits hypergraph edges that are multisets rather than sets. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version. 2. The reductions to the case of prime $r$ in the proofs Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of $r$. Currently we have no valid proof for the lower bound result in the other cases. We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• A generalized Kneser conjecture
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Generalized Kneser coloring theorems with combinatorial proofs
• On chromatic number of graphs and set-systems
• The Chromatic Number of Kneser Hypergraphs
• Topological lower bounds for the chromatic number: a hierarchy

Cited in

(11)

• A new coloring theorem of Kneser graphs
• Hedetniemi's conjecture for Kneser hypergraphs
• On the Chromatic Thresholds of Hypergraphs
• A note on \(b\)-coloring of Kneser graphs
• On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs
• Intersection patterns of finite sets and of convex sets
• scientific article; zbMATH DE number 3843775 (Why is no real title available?)
• On the generalized Erdős-Kneser conjecture: proofs and reductions
• Contraction, k-deficit, and the coloring of hypergraphs
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

This page was built for publication: On generalized Kneser hypergraph colorings

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