On the Chromatic Thresholds of Hypergraphs

DOI10.1017/S0963548315000061MaRDI QIDQ5366886zbMATH OpenFDO

Authors József Balogh, Ping Hu, John Lenz, Dhruv Mubayi, Jane V. Butterfield

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: 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 $$ 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 the so-called 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 that is based on the idea of Vapnik-Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these 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.

Recommendations

• The chromatic thresholds of graphs
• On chromaticity of hypergraphs
• A note on chromatic properties of threshold graphs
• Hypergraphs with zero chromatic threshold
• On r-chromatic hypergraphs
• Chromatic capacities of graphs and hypergraphs
• On chromatic polynomials of hypergraphs
• Note on chromatic polynomials of the threshold graphs
• On the chromatic numbers of random hypergraphs
• Chromatic thresholds in dense random graphs

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• A generalized Kneser conjecture
• A hypergraph extension of Turán's theorem
• A hypergraph regularity method for generalized Turán problems
• A new generalization of the Erdős-Ko-Rado theorem
• A variant of the hypergraph removal lemma
• An exact Turán result for the generalized triangle
• Applications of the regularity lemma for uniform hypergraphs
• Dense graphs with small clique number
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• Extremal problems whose solutions are the blowups of the small Witt- designs
• Families of Non-disjoint subsets
• Generalized Kneser coloring theorems with combinatorial proofs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs with zero chromatic threshold
• On Triple Systems with Independent Neighbourhoods
• On a valence problem in extremal graph theory
• On generalized Kneser hypergraph colorings
• On the chromatic number of pentagon-free graphs of large minimum degree
• On the chromatic number of triangle-free graphs of large minimum degree
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the density of families of sets
• On the structure of linear graphs
• On the structure of triangle-free graphs of large minimum degree
• Regularity Lemma for k-uniform hypergraphs
• Stability theorems for cancellative hypergraphs
• Supersaturated graphs and hypergraphs
• The Chromatic Number of Kneser Hypergraphs
• The Turán number of the Fano plane
• The chromatic thresholds of graphs
• The co-degree density of the Fano plane
• The counting lemma for regular k‐uniform hypergraphs
• The maximum size of 3-uniform hypergraphs not containing a Fano plane
• Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data
• Triple Systems Not Containing a Fano Configuration
• Weighted multiply intersecting families

Cited in

(8)

• Threshold hypergraphs
• Hypergraphs with zero chromatic threshold
• On vertex independence number of uniform hypergraphs
• The degree threshold for covering with all the connected 3-graphs with 3 edges
• Note on chromatic polynomials of the threshold graphs
• Mantel's theorem for random hypergraphs
• Positive codegree Andrásfai-Erdős-Sós theorem for the generalized triangle
• On r-chromatic hypergraphs

This page was built for publication: On the Chromatic Thresholds of Hypergraphs

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