Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T14:14:46.626Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Chromatic Thresholds of Hypergraphs

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  06 March 2015

JÓZSEF BALOGH ,
JANE BUTTERFIELD ,
PING HU ,
JOHN LENZ  and
DHRUV MUBAYI
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, Urbana-Champaign, IL 61801, USA (e-mail: [email protected], [email protected])
JANE BUTTERFIELD
Affiliation:
University of Victoria, Victoria BC V8P 5C2, Canada (e-mail: [email protected])
PING HU
Affiliation:
Department of Mathematics, University of Illinois, Urbana-Champaign, IL 61801, USA (e-mail: [email protected], [email protected])
JOHN LENZ
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: [email protected], [email protected])
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{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.

Łuczak and Thomassé 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án 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 non-degenerate hypergraphs whose Turán 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 fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre 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édi for graphs and might be of independent interest. Many open problems remain.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C65: Hypergraphs 05C15: Coloring of graphs and hypergraphs 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 2 , March 2016 , pp. 172 - 212
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Allen, P., Böttcher, J., Griffiths, S., Kohayakawa, Y. and Morris, R. (2013) The chromatic thresholds of graphs. Adv. Math. 235 261–295.CrossRefGoogle Scholar
[2] Alon, N., Frankl, P. and Lovász, L. (1986) The chromatic number of Kneser hypergraphs. Trans. Amer. Math. Soc. 298 359–370.Google Scholar
[3] Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 205–218.Google Scholar
[4] Balogh, J. and Lenz, J. Hypergraphs with zero chromatic threshold. Submitted.Google Scholar
[5] Brandt, S. and Thomassé, S. Dense triangle-free graphs are four colorable: A solution to the Erdős-Simonovits problem. J. Combin. Theory Ser. B, to appear.Google Scholar
[6] deAAAACaen, D. and Füredi, Z. (2000) The maximum size of 3-uniform hypergraphs not containing a Fano plane. J. Combin. Theory Ser. B 78 274–276.Google Scholar
[7] Erdős, P. and Simonovits, M. (1973) On a valence problem in extremal graph theory. Discrete Math. 5 323–334.Google Scholar
[8] Erdős, P. and Simonovits, M. (1983) Supersaturated graphs and hypergraphs. Combinatorica 3 181–192.Google Scholar
[9] Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.Google Scholar
[10] Frankl, P. and Füredi, Z. (1983) A new generalization of the Erdős–Ko–Rado theorem. Combinatorica 3 341–349.CrossRefGoogle Scholar
[11] Frankl, P. and Füredi, Z. (1989) Extremal problems whose solutions are the blowups of the small Witt-designs. J. Combin. Theory Ser. A 52 129–147.Google Scholar
[12] Frankl, P. and Tokushige, N. (2003) Weighted multiply intersecting families. Studia Sci. Math. Hungar. 40 287–291.Google Scholar
[13] Füredi, Z., Pikhurko, O. and Simonovits, M. (2005) On triple systems with independent neighbourhoods. Combin. Probab. Comput. 14 795–813.Google Scholar
[14] Füredi, Z. and Simonovits, M. (2005) Triple systems not containing a Fano configuration. Combin. Probab. Comput. 14 467–484.CrossRefGoogle Scholar
[15] Goddard, W. and Lyle, J. (2011) Dense graphs with small clique number. J. Graph Theory 66 319–331.Google Scholar
[16] Goldwasser, J. On the Turán number of {123, 124, 345}. Manuscript.Google Scholar
[17] Gowers, W. T. (2007) Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. of Math. (2) 166 897–946.Google Scholar
[18] Keevash, P. (2009) A hypergraph regularity method for generalized Turán problems. Random Struct. Alg. 34 123–164.CrossRefGoogle Scholar
[19] Keevash, P. (2011) Hypergraph Turán problems. In Surveys in Combinatorics 2011, Vol. 392 of London Math. Soc. Lecture Note Series, Cambridge University Press, pp. 83–139.CrossRefGoogle Scholar
[20] Keevash, P. and Mubayi, D. (2004) Stability theorems for cancellative hypergraphs. J. Combin. Theory Ser. B 92 163–175.Google Scholar
[21] Keevash, P. and Sudakov, B. (2005) The Turán number of the Fano plane. Combinatorica 25 561–574.CrossRefGoogle Scholar
[22] Kleitman, D. J. (1966) Families of non-disjoint subsets. J. Combin. Theory 1 153–155.Google Scholar
[23] Lange, C. E. M. C. and Ziegler, G. M. (2007) On generalized Kneser hypergraph colorings. J. Combin. Theory Ser. A 114 159–166.CrossRefGoogle Scholar
[24] Łuczak, T. (2006) On the structure of triangle-free graphs of large minimum degree. Combinatorica 26 489–493.Google Scholar
[25] Łuczak, T. and Thomassé, S. Coloring dense graphs via VC-dimension. Submitted.Google Scholar
[26] Mubayi, D. (2005) The co-degree density of the Fano plane. J. Combin. Theory Ser. B 95 333–337.CrossRefGoogle Scholar
[27] Mubayi, D. (2006) A hypergraph extension of Turán's theorem. J. Combin. Theory Ser. B 96 122–134.Google Scholar
[28] Nagle, B., Rödl, V. and Schacht, M. (2006) The counting lemma for regular k-uniform hypergraphs. Random Struct. Alg. 28 113–179.Google Scholar
[29] Pikhurko, O. (2008) An exact Turán result for the generalized triangle. Combinatorica 28 187–208.Google Scholar
[30] Pikhurko, O. (2013) Exact computation of the hypergraph Turán function for expanded complete 2-graphs. J. Combin. Theory Ser. B 103 220–225.Google Scholar
[31] Rödl, V. and Skokan, J. (2004) Regularity lemma for k-uniform hypergraphs. Random Struct. Alg. 25 1–42.CrossRefGoogle Scholar
[32] Rödl, V. and Skokan, J. (2006) Applications of the regularity lemma for uniform hypergraphs. Random Struct. Alg. 28 180–194.CrossRefGoogle Scholar
[33] Sarkaria, K. S. (1990) A generalized Kneser conjecture. J. Combin. Theory Ser. B 49 236–240.Google Scholar
[34] Sauer, N. (1972) On the density of families of sets. J. Combin. Theory Ser. A 13 145–147.CrossRefGoogle Scholar
[35] Simonovits, M. (1974) Extremal graph problems with symmetrical extremal graphs: Additional chromatic conditions. Discrete Math. 7 349–376.Google Scholar
[36] Tao, T. (2006) A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 1257–1280.Google Scholar
[37] Thomassen, C. (2002) On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica 22 591–596.CrossRefGoogle Scholar
[38] Thomassen, C. (2007) On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica 27 241–243.Google Scholar
[39] Vapnik, V. N. and Chervonenkis, A. Y. (1971) Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data. Avtomat. i Telemeh. (2) 42–53.Google Scholar
[40] Ziegler, G. M. (2002) Generalized Kneser coloring theorems with combinatorial proofs. Invent. Math. 147 671–691.Google Scholar