Pith. sign in

REVIEW 2 major objections 5 minor 53 references

Ramsey with purple edges

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that purple edges — edges coloured both red and blue — can be packed asymptotically exactly as densely as the Ramsey–Turán bound permits.

desk verdict A genuinely new Ramsey parameter with clean asymptotic results; the load-bearing gap is an unproved 'easy extraction' from FGM that supports only the sublinear part of the triangle theorem. read the letter →

arxiv 2505.01034 v2 pith:V5MVLAVP submitted 2025-05-02 math.CO

Thomas Lesgourgues , Anita Liebenau , Nye Taylor This is my paper · ORCID
classification math.CO MSC 05C5505C3505D10
keywords RamseynumberspurpleedgesRamsey-Turántriangle-freeprocessAndrásfaiconjectureblow-upcolouringindependencenumberextremalgraphtheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A purple edge is one coloured both red and blue. The paper studies $g(n;s,t)$, the largest number of purple edges in a colouring of $K_n$ that contains no red/purple $K_s$ and no blue/purple $K_t$, for $n

What carries the argument

The central tool is the blow-up colouring. Take a $k$-vertex graph $G$ that is $K_s$-free and has small independence number, replace each vertex by a balanced set, colour the cross-edges that follow $G$'s embedding red, every other cross-edge purple, and all edges inside the parts blue. This produces $\omega(R\cup P)=\omega(G)$, $\alpha(R)\le\lceil n/k\rceil\alpha(G)$, and $|P|\approx e(G)n^2/k^2$. Since $|P|\le |R\cup P|\le RT_s(n,t)$ is trivial, the equality $g\approx RT_s$ reduces to finding seed graphs with the right edge-to-independence trade-off: regular triangle-free graphs whose independence number equals their degree for $c<1/3$, Andrásfai graphs and their blow-ups for $c>1/3$, K4-free graphs with small independence number for even cliques, and triangle-free-process outputs for the sublinear range.

What would settle it

Simulate the triangle-free process on $n$ vertices up to $m^*(\varepsilon)=\left(\frac12\sqrt2-\varepsilon\right)n^{3/2}\sqrt{\log n}$ for small $\varepsilon>0$; if, while the process is still alive, the empirical probability that $\alpha(G_m)\ge(\sqrt2+10\sqrt\varepsilon)\sqrt{n\log n}$ exceeds $e^{-\sqrt n}$ by a non-negligible amount, the strengthened independence claim used for Theorem 4.4 is false.

Watch

Extended reading notes

Core claim

For every integer $s\ge3$ and all sufficiently small $c>0$, $$g(n;s,cn)=(1-o(1))\,RT_s(n,cn).$$ In words: when the forbidden blue clique is linear in $n$, the maximum number of mutually red-and-blue edges is asymptotically the maximum number of edges in a $K_s$-free graph whose independence number is just below $cn$. The proof matches the trivial upper bound with blow-up colourings seeded by Ramsey–Turán extremal graphs. For $s=3$ the same identity holds unconditionally for all $c\in(0,1]\setminus(1/3,4/11)$, and under the Andrásfai conjecture also in the missing interval; for sublinear $t$ the paper establishes weaker but still positive proportions of the Ramsey–Turán maximum.

Load-bearing premise

The load-bearing premise is that the triangle-free process, at the stopping time $m^*(\varepsilon)$, satisfies $\alpha(G_m) < (\sqrt2+10\sqrt\varepsilon)\sqrt{n\log n}$ with probability at least $1-e^{-\sqrt n}$ whenever the process has not already failed; the paper cites this as 'easily extracted' from a known proof but does not display the extraction.

Editorial extensions

If this is right

  • For every fixed $s\ge3$ and every sufficiently small $c>0$, the maximum number of purple edges in an $(s,cn)$-free red/blue/purple colouring is asymptotically $RT_s(n,cn)$: the trivial upper bound $|P|\le |R\cup P|$ is tight.
  • For triangles, the same asymptotic equality holds unconditionally for all $c\in(0,1]\setminus(1/3,4/11)$; if the Andrásfai conjecture is true, it holds for every constant $c\in(0,1/2]$.
  • When $t=(1+\varepsilon)\sqrt{2n\log n}$, there are colourings with $g(n;3,t)\ge \delta\,RT_3(n,t)$ for a positive $\delta$, and when $t\gg\sqrt{n\log n}$, $g(n;3,t)\ge (1/2-o(1))RT_3(n,t)$.
  • The lower bound on $t$ is essentially best possible: known Ramsey upper bounds make $g(n;3,t)$ undefined for $t\le\gamma\sqrt{n\log n}$ with $\gamma<1/\sqrt2$, and if the conjectured tight lower bound on $R(3,t)$ is correct the range is essentially complete.
  • Assuming the conjectured growth of Ramsey numbers, $g(n;s,t)$ is $\Theta(n^2)$ when $t\ge R^{-1}((s+1)/2,n)\log n$ and $o(n^2)$ when $t\le R^{-1}((s+3)/2,n)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The blow-up colouring is a transfer principle: whenever the extremal $K_s$-free graph with independence number below $t$ is a balanced blow-up of a small seed graph, the equality $g\approx RT_s$ should follow automatically; this suggests the same mechanism could extend to other forbidden subgraphs whose extremal graphs are blow-up-like.
  • The sublinear regime between $t=\sqrt{2n\log n}$ and $t=4\sqrt{n\log n}$ is the part of the triangle story most sensitive to the fine detail of the random process; a direct construction avoiding the extracted independence claim would either close the gap to $\gamma=\sqrt2$ or reveal a genuine drop in $g$ near the Ramsey threshold.
  • The small computational data suggest a testable pattern: when the $n=R(s,t)-1$ critical colouring is unique, a matching of purple edges suffices, whereas in cases with many critical colourings, sparse non-matching purple graphs win; studying the 'swappable-edge' structure of Ramsey-critical graphs could predict where matchings fail.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The manuscript introduces a red/blue/purple Ramsey parameter g(n;s,t), the maximum number of 'purple' edges in a colouring of K_n with no red/purple K_s and no blue/purple K_t, defined for n<R(s,t). The main results are asymptotic formulas comparing g to Ramsey--Turán numbers: Theorem 1.3 gives g(n;s,cn)=(1-o(1))RT_s(n,cn) for small c; Theorem 1.4 gives the triangle case for all linear c except the interval (1/3,4/11) (conditionally on the Andrásfai conjecture inside it), and gives sublinear lower bounds via the triangle-free process; Theorem 1.6 gives a general probabilistic lower bound; Theorem 1.8 gives a conditional Θ(n^2) versus o(n^2) dichotomy. The paper also reports small computational values of a matching variant g_M.

Significance. The paper identifies a natural three-colour Ramsey parameter and shows a close, mostly asymptotic, connection with Ramsey--Turán numbers. The upper bound (1.1) is immediate, so the value of the paper lies in the lower-bound constructions, which use explicit blow-ups, Andrásfai graphs, and the triangle-free process, and which are described in detail with error terms. The results are broad and, if fully supported, constitute a substantial contribution to extremal Ramsey theory. The computational section is a useful supplement. However, the sublinear triangle part of Theorem 1.4(ii) depends on an unproved 'easy extraction' from the Fiz Pontiveros--Griffiths--Morris memoir, which is a load-bearing gap in the current version.

major comments (2)
  1. [Section 4, Theorem 4.3(ii) and Theorem 4.4] Theorem 4.4, and hence the first part of Theorem 1.4(ii), relies on Theorem 4.3(ii), which is asserted as an 'easy extraction' from [24, Section 7.7] with no theorem number and no derivation. This statement is load-bearing: it must hold at the intermediate deterministic time m1=m*(ε1) with failure probability e^{-√n}, and it is applied after conditioning on E(m2). Please supply the extraction in the text or cite a precise theorem in [24] that implies exactly this form.
  2. [Section 4, proof of Theorem 4.4] The conditioning step uses the implication that E(m2) implies E(m1) when m2>m1. The events E(m) are never defined in the manuscript. If E(m) is an intersection of good events over the first m steps, this monotonicity is immediate, but it should be stated explicitly; as written, the conditioning argument is incomplete.
minor comments (5)
  1. [Section 3, proof of Theorem 1.4(i)] The case c=1/2 is not covered by Corollary 2.4, since the Turán graph T_{n,2} has independence number ⌈n/2⌉ ≥ cn for c=1/2. Please add a brief argument for this endpoint, for example using the canonical C5 blow-up with t=n/2−1.
  2. [Section 5.2, Theorem 1.6] The theorem is stated with a closed interval t ∈ [R^{-1}(s,n) log n, n], but at the lower endpoint t/log n = R^{-1}(s,n) there is no K_s-free graph with α(G) < t/log n under the paper's strict definition of RT_s. Please state the range with a strict inequality or clarify the convention used for RT_s(n,t) at boundary or real parameters.
  3. [Section 5.1, Theorem 5.3] The proof of Theorem 5.3 uses the quantitative form of Theorem 5.2 with an explicit relation between ε, a, and k, which the paper says is 'easily extracted' from [25]. Since this precise statement is used in (5.1)-(5.2), please include the statement or a short derivation.
  4. [Section 1, Definition 1.2] The sentence defining g contains a small wording issue: 'the largest integer such that there exists ... and |P|=g' is circular; it should be rephrased as 'the largest g such that there exists ... with |P|=g'.
  5. [Section 2.2] The sentence 'RTs(n, cn) is known precisely for every c ≥ 1/(s−1)' is inaccurate under the strict definition α(G)<t used in the paper; it should say c > 1/(s−1), consistent with Corollary 2.4.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: g is compared against the independently defined Ramsey–Turán number via explicit constructions.

full rationale

The paper's central results compare the new parameter g(n;s,t) with the external benchmark RT_s(n,t), which is defined and studied in prior literature independently of this paper. The upper bound (1.1) is indeed definitional: any (s,t)-free colouring gives a K_s-free graph R∪P with independence number α(R∪P)=ω(B)<t, so |P|≤|R∪P|≤RT_s(n,t). But all lower bounds are supplied by explicit blow-up colourings of known extremal graphs: Brandt's regular triangle-free graphs, Andrásfai graph blow-ups, Fox–Loh–Zhao K_4-free graphs, and triangle-free process outputs. These constructions show that g reaches RT_s up to a vanishing error; they do not presuppose the value of g and do not fit any parameter to the quantity being claimed. The sublinear triangle case relies on the triangle-free process theorems of Bohman–Keevash and Fiz Pontiveros–Griffiths–Morris, none of whose authors overlap with the present paper, so the quoted 'easily extracted' strengthening of Theorem 4.3(ii) is a support or correctness concern, not a circular reduction. No equation in the paper reduces to its input by construction, and the self-citations that occur (e.g., to the authors' own conjectures) are not load-bearing in any derivation. The honest finding is therefore no significant circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper's contributions are conditional on a body of established Ramsey-Turán and triangle-free process results, none of which are proved here. The only genuinely unproved input the authors introduce is the 'easily extracted' strengthening of a result from [24], which is load-bearing for Theorem 4.4. The conjectures (Andrásfai, Conjecture 1.7) are clearly flagged as such.

assumptions (8)
  • domain assumption Asymptotic formulas for RT_s(n,cn) for small c (Theorem 2.7, due to Lúders and Reiher [34])
    Theorem 1.3 and the even/odd constructions in Section 5 rely directly on these known RT density formulas; if they were false, the claimed equality g=(1-o(1))RT would fail.
  • standard math Brandt's theorem on the density of d/k for triangle-free d-regular graphs with independence number d (Theorem 2.5)
    Used in Theorem 3.1 and the odd clique construction to provide base graphs with prescribed degree/independence ratio.
  • standard math Triangle-free process bounds of Bohman-Keevash and Fiz Pontiveros-Griffiths-Morris (Theorem 4.1)
    Used in Theorem 4.2 for t much larger than sqrt(n log n).
  • domain assumption Strengthened form of FGM Proposition 7.2 (Theorem 4.3(ii)) asserted without proof in Section 4
    The paper claims this is easily extracted from [24, Section 7.7] but gives no derivation; Theorem 4.4 depends on it. This is the weakest assumption.
  • standard math Shearer's independence bound for triangle-free graphs
    Used in Observation 1.5 to upper-bound g near sqrt(n log n) and in deriving the Ramsey upper bound.
  • domain assumption Andrásfai's Conjecture (Conjecture 2.6)
    Assumed for the middle range c in (1/3,4/11) of Theorem 1.4(i); unconditional parts use the known cases k=2,3,4.
  • domain assumption Conjecture 1.7 on the growth of Ramsey numbers
    Used in Theorem 1.8 to derive a Θ(n^2)/o(n^2) dichotomy for g with sublinear t.
  • standard math Fox-Loh-Zhao graph construction (Theorem 5.2)
    Used in the even clique construction to seed the K4-free part.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ramsey with purple edges." pith.science (2026). https://pith.science/paper/V5MVLAVP

@misc{pith2026250501034,
  author       = {Pith},
  title        = {Pith review of: Ramsey with purple edges},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V5MVLAVP}},
  note         = {Machine review of arXiv:2505.01034}
}
abstract

Motivated by a question of Angell, we investigate a variant of Ramsey numbers where some edges are coloured simultaneously red and blue, which we call purple. Specifically, we are interested in the largest number $g=g(n;s,t)$, for some $s$ and $t$ and $n<R(s,t)$, such that there exists a red/blue/purple colouring of $K_n$ with $g$ purple edges, with no red/purple copy of $K_s$ nor blue/purple copy of $K_t$. We determine $g$ asymptotically for a large family of parameters, exhibiting strong dependencies with Ramsey-Tur\'{a}n numbers.

Figures

Figures reproduced from arXiv: 2505.01034 by the authors.

Figure 2.1
Figure 2.1. This is an example of red and purple edges in a 10-blow-up co [PITH_FULL_IMAGE:figures/full_fig_p005_2_1.png] view at source ↗
Figure 2.2
Figure 2.2. Andr´asfai graphs Γ2, Γ3, Γ4, and Γ5. Importantly, Andr´asfai graphs are triangle-free k-regular graphs on 3k − 1 vertices with indepen￾dence number α(Γk) = k. We refer to [31, 33] for more background on Andr´asfai graphs. For kn/(3k−1) ≤ t < (k−1)n/(3k−4), we define, following [33], the “canonical” blow-up Γ(n; k, t) of Γk by replacing vertices 1, k, 2k in Γk with sets of (k − 1)n − (3k − 4)t vertices each, replaci… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 50 canonical work pages

  1. [24]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths, and R. Morris. The triangle-free process and the Ramsey number R(3, k). Memoirs of the American Mathematical Society , 263:v+125, 2020

    work page 2020

  2. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. A note on Ramsey numbers. Journal of Combinatorial Theory, Series A , 29(3):354–360, 1980

    work page 1980

  3. [2]

    Anastos, S

    M. Anastos, S. Das, Morris. P., and S. Rathke. Private Communic ation, 2024. Workshop of the Combinatorics and Graph Theory Research Group at FU Berlin

    work page 2024

  4. [3]

    Andr´ asfai

    B. Andr´ asfai. ¨Uber ein Extremalproblem der Graphentheorie. Acta Mathematica Hungarica , 13 (3-4):443–455, 1962

    work page 1962

  5. [4]

    D. Angell. Problem 1691. Parabola, 58(3):1, 2022

    work page 2022

  6. [5]

    Balogh, P

    J. Balogh, P. Hu, and M. Simonovits. Phase transitions in Ramsey– Tur´ an theory.Journal of Combinatorial Theory, Series B , 114:148–169, 2015

    work page 2015

  7. [6]

    Balogh, C

    J. Balogh, C. Chen, G. McCourt, and C. Murley. Ramsey–Tur´ an problems with small indepen- dence numbers. European Journal of Combinatorics , 118:103872, 2024

    work page 2024

  8. [7]

    T. Bohman. The triangle-free process. Advances in Mathematics , 221(5):1653–1677, 2009

    2009

Show all 53 references
  1. [8]

    Bohman and P

    T. Bohman and P. Keevash. Dynamic concentration of the triang le-free process. Random Struc- tures & Algorithms , 58(2):221–293, 2021

    2021

  2. [9]

    Bollob´ as and P

    B. Bollob´ as and P. Erd˝ os. On a Ramsey-Tur´ an type problem.Journal of Combinatorial Theory, Series B , 21(2):166–168, 1976

    1976

  3. [10]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan. Random graphs and branching processes. In Handbook of Large-Scale Random Networks, pages 15–115. Springer, 2009

    2009

  4. [11]

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

    2010

  5. [12]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An ex ponential improvement for diagonal Ramsey. arXiv preprint arXiv:2303.09521 , 2023

    2023 arXiv

  6. [13]

    D. Conlon. A new upper bound for diagonal ramsey numbers. Annals of Mathematics , pages 941–960, 2009

    2009

  7. [14]

    P. Erd˝ os. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society , 53(4):292–294, 1947

    1947

  8. [15]

    Erd˝ os and V

    P. Erd˝ os and V. T. S´ os. Some remarks on Ramsey’s and Tur´ an’s theorem. Combinatorial Theory and its Applications, II (Proc. Colloq., Balatonf¨ ured, 19 69), pages 395–404, 1970

    1970

  9. [16]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres. A combinatorial problem in geometr y. Compositio Mathematica, 2: 463–470, 1935

    1935

  10. [17]

    Erd˝ os and A

    P. Erd˝ os and A. Szemer´ edi. On a ramsey type theorem. Periodica Mathematica Hungarica , 2 (1-4):295–299, 1972

    1972

  11. [18]

    Erd˝ os, A

    P. Erd˝ os, A. Meir, V. T. S´ os, and P. Tur´ an. On some applications of graph theory II. Studies in pure mathematics. Papers presented to Richard Rad´ o (Aca demic Press, London, 1971) , pages 89–100, 1971

    1971

  12. [19]

    Erd˝ os, A

    P. Erd˝ os, A. Meir, V. T. S´ os, and P. Tur´ an. On some applications of graph theory, I. Discrete Mathematics, 2(3):207–228, 1972

    1972

  13. [20]

    Erd˝ os, A

    P. Erd˝ os, A. Meir, V. T. S´ os, and P. Tur´ an. On some applications of graph theory III. Canadian Mathematical Bulletin , 15(1):27–32, 1972

    1972

  14. [21]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, V. T. S´ os, and E. Szemer´ edi. More results on Ramsey-Tur´ an type problems. Combinatorica, 3:69–81, 1983

    1983

  15. [22]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, M. Simonovits, V. T. S´ os, and E Szemer´edi. Tur´ an-Ramsey theorems and simple asymptotically extremal structures. Combinatorica, 13:31–56, 1993

    1993

  16. [23]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, M. Simonovits, V. T. S´ os, and E. Szemer´ edi. Tur´ an-Ramsey theorems for Kp-stability numbers. Combinatorics, Probability and Computing , 3:297–325, 1994. 19

    1994

  17. [25]

    J. Fox, P. Loh, and Y. Zhao. The critical window for the classica l Ramsey-Tur´ an problem. Combinatorica, 35(4):435–476, 2015

    2015

  18. [26]

    Gauthier and C.E

    T. Gauthier and C.E. Brown. A formal proof of R(4, 5) = 25. In 15th International Conference on Interactive Theorem Proving (ITP 2024) , volume 309 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 16:1–16:18, 2024

    2024

  19. [27]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei. Optimizing the CGMS upp er bound on Ramsey numbers. arXiv preprint arXiv:2407.19026 , 2024

    2024 arXiv

  20. [28]

    J. Kim, Y. Kim, and H. Liu. Two conjectures in Ramsey–Tur´ an theory. SIAM Journal on Discrete Mathematics, 33(1):564–586, 2019

    2019

  21. [29]

    J. H. Kim. The Ramsey number R(3, t) has order of magnitude t2/ log t. Random Structures & Algorithms, 7(3):173–207, 1995

    1995

  22. [30]

    /suppress Luczak, J

    T. /suppress Luczak, J. Polcyn, and C. Reiher. Andr´ asfai and Vega graphs in Ramsey–Tur´ an theory. Journal of Graph Theory , 98(1):57–80, 2021

    2021

  23. [31]

    /suppress Luczak, J

    T. /suppress Luczak, J. Polcyn, and C. Reiher. On the Ramsey-Tur´ an density of triangles. Combinatorica, 42(1):115–136, 2022

    2022

  24. [32]

    /suppress Luczak, J

    T. /suppress Luczak, J. Polcyn, and C. Reiher. Strong Brandt-Thomass´ e theorems. arXiv preprint arXiv:2406.10745, 2024

    2024 arXiv

  25. [33]

    /suppress Luczak, J

    T. /suppress Luczak, J. Polcyn, and C. Reiher. The next case of Andr´ asfai’s conjecture. Journal of Com- binatorial Theory, Series B , 172:198–220, 2025

    2025

  26. [34]

    C. M. L¨ uders and C. Reiher. The Ramsey–Tur´ an problem for cliques. Israel Journal of Mathe- matics, 230:613–652, 2019

    2019

  27. [35]

    Mattheus and J

    S. Mattheus and J. Verstraete. The asymptotics of r(4,t). Annals of Mathematics, 199(2):919–941, 2024

    2024

  28. [36]

    B. D. McKay. Ramsey Graphs. https://users.cecs.anu.edu.au/~bdm/data/ramsey.html, 2025

    2025

  29. [37]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation , 60:94–112, 2014

    2014

  30. [38]

    B. D. McKay and S. P. Radziszowski. R(4, 5) = 25. Journal of Graph Theory , 19(3):309–322, 1995

    1995

  31. [39]

    B. D. McKay and S. P. Radziszowski. Subgraph counting identities and Ramsey numbers. Journal of Combinatorial Theory , 69, 1997

    1997

  32. [40]

    Z. L. Nagy. Density version of the Ramsey problem and the directed Ramsey problem. Australasian Journal of Combinatorics , 66(2):240–255, 2016

    2016

  33. [41]

    F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society , s2-30(1):264–286, 1930

    1930

  34. [42]

    V. R¨ odl. Upper bound on Ramsey numbers R(k, ℓ). Unpublished, 1986

    1986

  35. [43]

    A. Sah. Diagonal Ramsey via effective quasirandomness. Duke Mathematical Journal , 172(3):545 – 567, 2023

    2023

  36. [44]

    J. B. Shearer. A note on the independence number of triangle- free graphs. Discrete Mathematics, 46(1):83–87, 1983

    1983

  37. [45]

    Simonovits and V

    M. Simonovits and V. T. S´ os. Ramsey–Tur´ an theory.Discrete Mathematics , 229(1-3):293–340, 2001

    2001

  38. [46]

    J. Spencer. Ramsey’s theorem – a new lower bound. Journal of Combinatorial Theory, Series A , 18(1):108–115, 1975

    1975

  39. [47]

    J. Spencer. Maximal triangle-free graphs and Ramsey R(3,t). Unpublished manuscript , 1995. Available online at http://www.cs.nyu.edu/spencer/papers/ramsey3k.pdf

    1995

  40. [48]

    B. Sudakov. A few remarks on Ramsey–Tur´ an-type problems. Journal of Combinatorial Theory, Series B , 88(1):99–106, 2003

    2003

  41. [49]

    Szemer´ edi

    E. Szemer´ edi. On graphs containing no complete subgraph with 4 vertices. Matematikai Lapok, 23(113-116):2, 1972

    1972

  42. [50]

    SageMath, the Sage Mathematics Software System (Version 9

    The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9. 2), 2020. https://www.sagemath.org

    2020

  43. [51]

    Thomason

    A. Thomason. An upper bound for some Ramsey numbers. Journal of Graph Theory , 12(4): 20 509–517, 1988

    1988

  44. [52]

    P. Tur´ an. Eine Extremalaufgabe aus der Graphentheorie. Matematikai ´ es. Fizikai Lapok, 48: 436–452, 1941. A Pseudocodes We now present the pseudocodes used to compute results presented in Section

    1941

  45. [53]

    Algorithm 1 below takes as input a Ramsey(s, t)-graph G, and outputs the largest k such that a matching of size k in G can be deleted without creating an independent set of size t

    A Ramsey(s, t)-graph is a graph with no clique of size s, and no independent set of size t. Algorithm 1 below takes as input a Ramsey(s, t)-graph G, and outputs the largest k such that a matching of size k in G can be deleted without creating an independent set of size t. Algo...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.