Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T02:52:48.188Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Chromatic Thresholds of Hypergraphs

Part of: Extremal combinatorics Graph theory

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: jobal@math.uiuc.edu, pinghu1@math.uiuc.edu)
JANE BUTTERFIELD
Affiliation:
University of Victoria, Victoria BC V8P 5C2, Canada (e-mail: jvbutter@uvic.ca)
PING HU
Affiliation:
Department of Mathematics, University of Illinois, Urbana-Champaign, IL 61801, USA (e-mail: jobal@math.uiuc.edu, pinghu1@math.uiuc.edu)
JOHN LENZ
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: lenz@math.uic.edu, mubayi@math.uic.edu)
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: lenz@math.uic.edu, mubayi@math.uic.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 2 , March 2016 , pp. 172 - 212
Copyright
Copyright © Cambridge University Press 2015 

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