Stability with Minuscule Structure for Chromatic Thresholds

Abstract

The chromatic threshold

{\delta }_{\chi }(H)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\delta _\chi (H)$$\end{document}

of a graph H is the infimum of

d>0

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d>0$$\end{document}

such that the chromatic number of every n-vertex H-free graph with minimum degree at least dn is bounded by a constant depending only on H and d. Allen, Böttcher, Griffiths, Kohayakawa, and Morris determined the chromatic threshold for every H; in particular, they showed that if

\chi (H)=r\ge 3

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\chi (H)=r\ge 3$$\end{document}

, then

{\delta }_{\chi }(H)\in \{\frac{r-3}{r-2},\frac{2r-5}{2r-3},\frac{r-2}{r-1}\}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\delta _\chi (H) \in \{\frac{r-3}{r-2},~\frac{2 r-5}{2 r-3},~\frac{r-2}{r-1}\}$$\end{document}

. While the chromatic thresholds have been completely determined, rather surprisingly the structural behaviors of extremal graphs near the threshold remain unexplored. In this paper, we establish the stability theorems for chromatic threshold problems. We prove that every n-vertex H-free graph G with

\delta (G)\ge ({\delta }_{\chi }(H)-o(1))n

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\delta (G)\ge (\delta _\chi (H)-o(1))n$$\end{document}

and

\chi (G)=\omega (1)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\chi (G)=\omega (1)$$\end{document}

must be structurally close to one of the extremal configurations. Furthermore, we give a stronger stability result when H is a clique, showing that G admits a partition into independent sets and a small subgraph on a sublinear number of vertices. We show that this small subgraph has fractional chromatic number

2+o(1)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$2+o(1)$$\end{document}

and is homomorphic to a Kneser graph defined by subsets of a logarithmic size set; both these two bounds are best possible. This is the first stability result that captures the lower-order structural features of extremal graphs. We also study two variations of chromatic thresholds. Replacing chromatic number by its fractional counterpart, we determine the fractional chromatic thresholds for all graphs. Another variation is the bounded-VC chromatic thresholds, which was introduced by Liu, Shangguan, Skokan, and Xu very recently. Extending work of Łuczak and Thomassé on the triangle case, we determine the bounded-VC chromatic thresholds for all cliques.

Keywords

Chromatic thresholds / Stability / Kneser graphs / 05C35

References

[1] Allen P, Böttcher J, Griffiths S, Kohayakawa Y, Morris R. The chromatic thresholds of graphs. Adv. Math., 2013, 235: 261-295

[2] Andrásfai, B., Erdős, P., Sós, V.T.: On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8(3), 205–218 (1974)

[3] Balogh J, Clemen FC, Lavrov M, Lidický B, Pfender F. Making Kr+1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$K_{r+1}$$\end{document}-free graphs r\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$r$$\end{document}-partite. Comb. Probab. Comput., 2021, 30(4): 609-618

[4] Bourneuf, R., Charbit, P., Thomassé, S.: A dense neighborhood lemma: Applications of partial concept classes to domination and chromatic number. arXiv:2504.02992v2 (2025)

[5] Brandt S. On the structure of dense triangle-free graphs. Comb. Probab. Comput., 1999, 8(3): 237-245

[6] Chen, C.C., Jin, G.P., Koh, K.M.: Triangle-free graphs with large degree. Comb. Probab. Comput. 6(4), 381–396 (1997)

[7] Ebsen O, Schacht M. Homomorphism thresholds for odd cycles. Combinatorica, 2020, 40(1): 39-62

[8] Erdős P. Graph theory and probability. Can. J. Math., 1959, 11: 34-38

[9] Erdős, P., Hajnal, A.: On chromatic number of infinite graphs. In: Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 83–98. Academic Press, New York-London (1968)

[10] Erdős, P., Simonovits, M.: A limit theorem in graph theory. Studia Sci. Math. Hungar 1, 51–57 (1966)

[11] Erdős, P., Simonovits, M.: On a valence problem in extremal graph theory. Discrete Math. 5(4), 323–334 (1973)

[12] Erdős P, Simonovits M. Supersaturated graphs and hypergraphs. Combinatorica, 1983, 3(2): 181-192

[13] Füredi, Z.: A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity. J. Combin. Theory Ser. B 115, 66–71 (2015)

[14] Goddard, W., Lyle, J.: Dense graphs with small clique number. J. Graph Theory 66(4), 319–331 (2011)

[15] Häggkvist, R.: Odd cycles of specified length in non-bipartite graphs. In: Graph Theory (Proc. Conf. Graph Theory, Cambridge), North-Holland Math. Stud., vol. 62, pp. 89–99. North-Holland, Amsterdam (1982)

[16] Haussler, D., Welzl, E.: ε\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\varepsilon }$$\end{document}-nets and simplex range queries. Discrete Comput. Geom. 2(2), 127–151 (1987)

[17] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13–30 (1963)

[18] Huang, X., Liu, H., Rong, M., Xu, Z.: Interpolating chromatic and homomorphism thresholds. arXiv:2502.09576 (2025)

[19] Illingworth F. Minimum degree stability of H\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$H$$\end{document}-free graphs. Combinatorica, 2023, 43(1): 129-147

[20] Jin, G.: Triangle-free four-chromatic graphs. Discrete Math. 145(1–3), 151–170 (1995)

[21] Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability (New Haven, Conn., 1982), Contemp. Math., vol. 26, pp. 189–206. American Mathematical Society, Providence, RI (1984)

[22] Kim, J., Liu, H., Pikhurko, O., Sharifzadeh, M.: Asymptotic structure for the clique density theorem. Discrete Anal. 2020, Paper No. 19, 26 pp. (2020)

[23] Komlós, J., Simonovits, M.: Szemerédi’s regularity lemma and its applications in graph theory. In: Combinatorics, Paul Erdős Is Eighty, Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud., vol. 2, pp. 295–352. János Bolyai Math. Soc., Budapest (1996)

[24] Liu, H., Pikhurko, O., Sharifzadeh, M., Staden, K.: Stability from graph symmetrisation arguments with applications to inducibility. J. Lond. Math. Soc. (2) 108(3), 1121–1162 (2023)

[25] Liu, H., Shangguan, C., Skokan, J., Xu, Z.: Beyond chromatic threshold via the (p,q)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(p, q) $$\end{document}-theorem, and a sharp blow-up phenomenon. arXiv:2403.17910v3 (2024)

[26] Lovász L. Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 1978, 25(3): 319-324

[27] Łuczak, T., Thomassé, S.: Coloring dense graphs via VC-dimension. arXiv:1007.1670 (2010)

[28] Lyle, J.: On the chromatic number of H\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$H$$\end{document}-free graphs of large minimum degree. Graphs Combin. 27(5), 741–754 (2011)

[29] Nikiforov, V.: Chromatic number and minimum degree of Kr\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$K_r$$\end{document}-free graphs. arXiv:1001.2070 (2010)

[30] Ren, S., Wang, J., Wang, S., Yang, W.: A stability result for C2k+1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$C_{2k+1}$$\end{document}-free graphs. SIAM J. Discrete Math. 38(2), 1733–1756 (2024)

[31] Scheinerman ER, Ullman DH. Fractional Graph Theory—A Rational Approach to the Theory of Graphs, 1997, New York, John Wiley & Sons

[32] Simonovits, M.: A method for solving extremal problems in graph theory, stability problems. In: Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279–319. Academic Press, New York (1968)

[33] Thomassen C. On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica, 2002, 22(4): 591-596

[34] Thomassen C. On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica, 2007, 27(2): 241-243

[35] Tran T. On the structure of large sum-free sets of integers. Israel J. Math., 2018, 228(1): 249-292

[36] Turán, P.: Eine extremalaufgabe aus der graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)

[37] Zykov, A.A.: On some properties of linear complexes. Mat. Sbornik N.S. 24(2), 163–188 (1949) (in Russian)

Funding

Institute for Basic Science(IBS-R029-C4)

National Research Foundation of Korea(RS-2023-00210430)

Natural Science Foundation of China(12231014)

MICIU/AEI(10.13039/501100011033)

China Scholarship Council(12501486)

RIGHTS & PERMISSIONS

Peking University

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.