On the Chromatic Thresholds of Hypergraphs

Details On the Chromatic Thresholds of Hypergraphs On the Chromatic Thresholds of Hypergraphs

2011-03-08

arxiv.org/abs/1103.1416v3

Mathematics

Combinatorics

37 pages, 3 figures

Scientific paper

Let F be a family of r-uniform hypergraphs. The chromatic threshold of F is the infimum of all non-negative reals c such that the subfamily of F comprising hypergraphs H with minimum degree at least $c \binom{|V(H)|}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r=2), and in this paper we begin its systematic study for hypergraphs. {\L}uczak and Thomass\'e recently proved that the chromatic threshold of near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Tur\'an number is achieved uniquely by the complete (r+1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of nondegenerate hypergraphs whose Tur\'an number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle. In order to prove upper bounds we introduce the concept of fiber bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fiber bundle dimension, a structural property of fiber bundles which is based on the idea of Vapnik-Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a generalized Kneser hypergraph. Using methods from extremal set theory, we prove that these generalized Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemer\'edi for graphs and might be of independent interest. Many open problems remain.

Affiliated with

Also associated with

No associations

Rating

On the Chromatic Thresholds of Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Chromatic Thresholds of Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Chromatic Thresholds of Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81886