pith. sign in

arxiv: 2409.04042 · v3 · submitted 2024-09-06 · 🧮 math.CO

A step towards the Ramsey-Tur\'{a}n conjecture for K₃ and K₆

Xinyu Hu , Qizhong Lin This is my paper

Pith reviewed 2026-05-23 21:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey-Turán numbers(K3,K6)-free graphsindependence numberSzemerédi's regularity lemmastability argumentextremal graph theorycolored forbidden subgraphs
0
0 comments X

The pith

The paper proves ρ(3,6,δ) ≤ 5/12 + δ/2 + 2.1025δ² for all sufficiently small δ > 0.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to bound the asymptotic density of edges in graphs that avoid a red K3 and a blue K6 while keeping the independence number at most δn. It establishes an upper bound on the limiting density ρ(3,6,δ) that comes within a small additive error of a matching lower-bound construction. A sympathetic reader would care because this supplies the first quantitative progress toward a 2019 conjecture that the exact density is 5/12 + δ/2 + 2δ², thereby narrowing the possible asymptotic behavior of these colored extremal numbers.

Core claim

Using Szemerédi's regularity lemma together with a stability argument, the authors show that for every sufficiently small δ > 0 the Ramsey-Turán density satisfies ρ(3,6,δ) ≤ 5/12 + δ/2 + 2.1025δ². This supplies the first upper bound that is of the same form as the known construction lower bound ρ(3,6,δ) ≥ 5/12 + δ/2 + 2δ².

What carries the argument

Szemerédi's regularity lemma combined with a stability argument that controls the possible edge distribution in a (K3,K6)-free graph whose independence number is at most δn.

If this is right

  • The gap between the proven upper bound and the conjectured exact density is confined to the coefficient of the δ² term.
  • Any future improvement that reduces the coefficient from 2.1025 to 2 would confirm the 2019 conjecture for small δ.
  • The method yields an explicit, albeit large, threshold beyond which the inequality holds for all smaller positive δ.
  • The same regularity-plus-stability approach can be examined for other pairs (p,q) where a matching construction is already known.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Refining the stability analysis or replacing the regularity lemma with a more modern counting lemma might shrink the 2.1025 coefficient.
  • The result suggests that the extremal graphs for small δ are close in structure to the blow-up of a particular 5-vertex graph used in the lower-bound construction.
  • If the same technique applies to larger cliques, it could produce quantitative versions of other open Ramsey-Turán conjectures.

Load-bearing premise

The stability argument combined with Szemerédi's regularity lemma produces a quantitative bound whose error terms can be absorbed into the specific coefficient 2.1025 without requiring additional assumptions on the graph beyond the (K3,K6)-free and α(G) ≤ δn conditions.

What would settle it

A sequence of (K3,K6)-free n-vertex graphs with independence number at most δn whose edge count exceeds (5/12 + δ/2 + 2.1025δ²)n² for arbitrarily small δ > 0 would falsify the claimed upper bound.

read the original abstract

Ramsey-Tur\'{a}n type problems were initiated by Erd\H{o}s and S\'{o}s in 1969. Given integers $p, q\ge2$, a graph $G$ is $(K_p,K_q)$-free if there exists a red/blue edge coloring of $G$ such that it contains neither a red $K_p$ nor a blue $K_q$. For any $\delta>0$, the Ramsey-Tur\'{a}n number $RT( {n,p,q,\delta n)} $ is the maximum number of edges in an $n$-vertex $(K_p,K_q)$-free graph with independence number at most $\delta n$. Let $\rho (p, q,\delta ) = \mathop {\lim }\limits_{n \to \infty } \frac{RT(n,p, q,\delta n)}{n^2}$. Kim, Kim and Liu (2019) showed that $\rho(3,6,\delta)\ge \frac{5}{12}+\frac{\delta}{2}+2\delta^2$ via a skillful construction and conjectured the equality holds for sufficiently small $\delta>0$. Using Szemer\'{e}di's regularity lemma and a stability argument, we make the first step towards the conjecture by showing that $\rho(3,6,\delta)$ is at most $\frac{5}{{12}} + \frac{\delta }{2}+ 2.1025\delta ^2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to prove that the Ramsey-Turán density satisfies ρ(3,6,δ) ≤ 5/12 + δ/2 + 2.1025 δ² for all sufficiently small δ > 0. The argument applies Szemerédi's regularity lemma to a 2-edge-colored graph that is red-K₃-free and blue-K₆-free with α(G) ≤ δn, obtains an equitable partition, and invokes a stability result to bound the edges of the cluster graph by the conjectured extremal value plus an additive error that is absorbed into the quadratic term.

Significance. If the quantitative absorption of error terms succeeds, the result supplies the first upper bound matching the Kim-Kim-Liu lower-bound construction up to the quadratic coefficient (with a slightly worse constant 2.1025). It demonstrates that the standard regularity-plus-stability toolkit can be made to yield an explicit numerical bound in this Ramsey-Turán setting and therefore constitutes a concrete, non-trivial step toward the conjectured equality.

major comments (1)
  1. [Proof of the main theorem (error analysis following the regularity lemma application)] The absorption of all error terms (irregular pairs, o(1) discrepancy in the cluster-graph edge count, and the translation of α(G) ≤ δn into the reduced graph) into the specific coefficient 2.1025 must be verified explicitly. The manuscript asserts that these errors are ≤ 0.1025 δ² n² once ε(δ) is chosen sufficiently small, but the load-bearing step is the concrete calculation showing that no hidden linear-in-δ term survives; without this verification the claimed numerical bound is not justified.
minor comments (1)
  1. [Abstract] The abstract states the numerical constant 2.1025 without indicating the section in which the error-budget calculation appears.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the single major comment below and will incorporate the requested verification in the revision.

read point-by-point responses

  1. Referee: The absorption of all error terms (irregular pairs, o(1) discrepancy in the cluster-graph edge count, and the translation of α(G) ≤ δn into the reduced graph) into the specific coefficient 2.1025 must be verified explicitly. The manuscript asserts that these errors are ≤ 0.1025 δ² n² once ε(δ) is chosen sufficiently small, but the load-bearing step is the concrete calculation showing that no hidden linear-in-δ term survives; without this verification the claimed numerical bound is not justified.

    Authors: We agree that an explicit, self-contained verification of the error absorption is required to justify the numerical coefficient. In the revised manuscript we will add a new appendix (or expanded subsection) that carries out the concrete calculation: we bound the contribution of irregular pairs (at most ε n²), the discrepancy between the original and cluster-graph edge counts (controlled by the regularity parameter), and the translation of α(G) ≤ δn into an independence-number bound on the reduced graph. We then show that, by first fixing δ > 0 small and then choosing ε = ε(δ) sufficiently small, the total additive error is at most 0.1025 δ² n² and contains no surviving linear-in-δ term. This calculation will be written out with explicit constants so that the claimed upper bound ρ(3,6,δ) ≤ 5/12 + δ/2 + 2.1025 δ² is fully justified. revision: yes

Circularity Check

0 steps flagged

No circularity: upper bound derived from regularity lemma and stability without reduction to inputs

full rationale

The paper proves an upper bound on ρ(3,6,δ) via Szemerédi's regularity lemma applied to 2-edge-colored graphs and a stability argument that bounds edges in the cluster graph. The coefficient 2.1025 is selected explicitly to absorb additive error terms arising from irregular pairs, o(1) terms, and the translation of α(G) ≤ δn; this is a standard quantitative verification, not a fit or self-definition. The matching lower bound and conjecture are cited from the independent 2019 work of Kim, Kim and Liu. No step reduces by construction to the claimed result, no self-citation is load-bearing for the central inequality, and the derivation chain remains self-contained against external combinatorial tools.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof invokes Szemerédi's regularity lemma (standard_math) and a stability argument whose quantitative error control is not detailed in the abstract. No free parameters or invented entities are visible from the given text.

axioms (1)
  • standard math Szemerédi's regularity lemma applies to any graph and produces an equitable partition with controlled irregularity
    Invoked in the abstract to obtain the upper bound

pith-pipeline@v0.9.0 · 5810 in / 1368 out tokens · 24457 ms · 2026-05-23T21:07:49.780373+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs,Com- binatorica 20 (2000), 451–476

    work page 2000

  2. [2]

    Balogh, P

    J. Balogh, P. Hu, and M. Simonovits, Phase transitions in the Ramsey-Turán theory,J. Combin. Theory Ser. B114 (2015), 148–169

    work page 2015

  3. [3]

    Balogh, H

    J. Balogh, H. Liu, and M. Sharifzadeh, On two problems in Ramsey-Turán theory,SIAM J. Discrete Math31 (2017), 1848–1866

    work page 2017

  4. [4]

    Bollobás and P

    B. Bollobás and P. Erdős, On a Ramsey-Turán type problem,J. Combin. Theory Ser. B21 (1976), 166–168

    work page 1976

  5. [5]

    310 (2010), 662–669

    S.Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math. 310 (2010), 662–669

    work page 2010

  6. [6]

    W. G. Brown, P. Erdős and M. Simonovits, Extremal problems for directed graphs,J. Combin. Theory Ser. B15 (1973), 77–93

    work page 1973

  7. [7]

    Balogh, H

    J. Balogh, H. Liu and M. Sharifzadeh, On two problems in Ramsey-Turán theory,SIAM J. Discrete math.31 (2017), 1848–1866

    work page 2017

  8. [8]

    Codish, M

    M. Codish, M. Frank, A. Itzhakov and A. Miller, Computing the Ramsey NumberR(4, 3, 3) Using Abstraction and Symmetry Breaking,Constraints 21 (2016), 375–393

    work page 2016

  9. [9]

    Conlon, The Ramsey number of books,Adv

    D. Conlon, The Ramsey number of books,Adv. Combin.3 (2019), 12pp

    work page 2019

  10. [10]

    Conlon, J

    D. Conlon, J. Fox and Y. Wigderson, Ramsey number of books and quasirandomness, Combinatorica 42 (2022), no. 3, 309–363. 28

    work page 2022

  11. [11]

    Erdős, Graph theory and probability II,Canad

    P. Erdős, Graph theory and probability II,Canad. J. Math.13 (1961), 346–352

    work page 1961

  12. [12]

    Erdős, A

    P. Erdős, A. Hajnal, M. Simonovits, V. Sós and E. Szemerédi, Turán-Ramsey theorems and Kp-independnece numbers,Combin. Probab. Comput.3 (1994), 297–325

    work page 1994

  13. [13]

    Erdős, A

    P. Erdős, A. Hajnal, M. Simonovits, V. Sós and E. Szemerédi, Turán-Ramsey theorems and simple asymptotically extremal structures,Combinatorica 13 (1993), 31–56

    work page 1993

  14. [14]

    Erdős, A

    P. Erdős, A. Hajnal, V. Sós and E. Szemerédi, More results on Ramsey-Turán type problems, Combinatorica 3 (1983), 69–81

    work page 1983

  15. [15]

    Erdős and C

    P. Erdős and C. A. Rogers, The construction of certain graphs,Canadian J. Math14 (1962), 702–707

    work page 1962

  16. [16]

    Erdős and V

    P. Erdős and V. T. Sós, some remarks on Ramsey’s and Turán’s theorem, in Combinato- rial Theory and Its Applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, 395–404

    work page 1969

  17. [17]

    Erdős, On the graph theorem of Turán,Mat

    P. Erdős, On the graph theorem of Turán,Mat. Lapok21 (1970), 249–251 (in Hungarian)

    work page 1970

  18. [18]

    Erdős and V

    P. Erdős and V. T. Sós, On Turán-Ramsey’s type theorems, II,Stud. Sci. Math. Hung.14 (1979), 27–36

    work page 1979

  19. [19]

    Erdős and A

    P. Erdős and A. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.52 (1946), 1087–1091

    work page 1946

  20. [20]

    Füredi, A proof of the stability of extremal graphs, Simonovits’stability from Szemerédi’s regularity,J

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

    work page 2015

  21. [21]

    J. Fox, P. Loh, and Y. Zhao, The critical window for the classical Ramsey-Turán problem, Combinatorica 35 (2015), 435–476

    work page 2015

  22. [22]

    Fox and B

    J. Fox and B. Sudakov, Dependent random choice,Random Structures Algorithms38 (2011), 68–99

    work page 2011

  23. [23]

    R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs,Canad. J. Math.7 (1955), 1–7

    work page 1955

  24. [24]

    Hu and Q

    X. Hu and Q. Lin, Two-colored Ramsey-Turán densities involving triangles,SIAM J. Dis- crete Math.38 (2024), 2132–2162

    work page 2024

  25. [25]

    J. H. Kim, The Ramsey numberR(3, t) has order of magnitudet2/ log t, Random Structures Algorithms 7 (1995), 173–207

    work page 1995

  26. [26]

    J. Kim, Y. Kim and H. Liu, Two conjectures in Ramsey-Turán theory,SIAM J. Discrete Math. 33 (2019), 564–586

    work page 2019

  27. [27]

    Komlós and M

    J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications to graph theory.Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295–352, Bolyai Soc. Math. Stud., 2,János Bolyai Math. Soc., Budapest, 1996

    work page 1993

  28. [28]

    Li and Q

    Y. Li and Q. Lin, Elementary methods of graph Ramsey theory, Springer, 2022. 29

    work page 2022

  29. [29]

    Liu and Y

    M. Liu and Y. Li, Two results on Ramsey-Turán numbers,Electron. J. Combin.28 (2021), no. 4, Paper No. 4.6, 8 pp

    work page 2021

  30. [30]

    C. M. Lüders and C. Reiher, The Ramsey-Turan problem for cliques,Israel J. Math.230 (2019), no. 2, 613–652

    work page 2019

  31. [31]

    Radziszowski, Small Ramsey numbers, Electron

    S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994), a dynamic survey

    work page 1994

  32. [32]

    F. P. Ramsey, On a problem of formal logic,Proc. Lond. Math. Soc.30 (1929), 264–286

    work page 1929

  33. [33]

    Simonovits and V

    M. Simonovits and V. Sós, Ramsey-Turán theory,Discrete Math.229 (2001), 293–340

    work page 2001

  34. [34]

    Sudakov, A few remarks on the Ramsey-Turán-type problems,J

    B. Sudakov, A few remarks on the Ramsey-Turán-type problems,J. Combin. Theory Ser. B 88 (2003), 99–106

    work page 2003

  35. [35]

    Szemerédi, Regular partitions of graphs, in: Problèmes Combinatories et théorie des graphs, Colloque Inter

    E. Szemerédi, Regular partitions of graphs, in: Problèmes Combinatories et théorie des graphs, Colloque Inter. CNRS, Univ. Orsay, Orsay, 1976, J. Bermond, J. Fournier, M. Las Vergnas, and D. Scotteau, Eds. (1978), pp. 399–402

    work page 1976

  36. [36]

    Szemerédi, On graphs containing no complete subgraph with4 vertices, Mat

    E. Szemerédi, On graphs containing no complete subgraph with4 vertices, Mat. Lapok23 (1972), 113–116

    work page 1972

  37. [37]

    Turán, Eine Extremalaufgabe aus der Fraphentheorie,Mat

    P. Turán, Eine Extremalaufgabe aus der Fraphentheorie,Mat. Fiz. Lapok48 (1941), 436– 452

    work page 1941

  38. [38]

    Turán, On the theory of graphs,Colloq

    P. Turán, On the theory of graphs,Colloq. Math.3 (1954), 19–30. 30 Appendix All summations of the subscripts are taken modular 5. Define two functionsf and g as follows: f(x1, . . . , x5, y1, . . . , y5) = 3 10 5X i=1 xi ! + 1 5 5X i=1 yi ! + 5X i=1 xiyi+2 ! + 5X i=1 xixi+2 ! , and g(x1, . . . , x5) = 1 2 5X i=3 xi ! + 5X i=1 xixi+2 ! . The domains off an...

    work page 1954