Bipartite cuts in Ramsey-Tur\'an style

Bernard Lidick\'y; Ce Chen; J\'ozsef Balogh

arxiv: 2606.20397 · v1 · pith:TPPL73YOnew · submitted 2026-06-18 · 🧮 math.CO

Bipartite cuts in Ramsey-Tur\'an style

J\'ozsef Balogh , Ce Chen , Bernard Lidick\'y This is my paper

Pith reviewed 2026-06-26 16:40 UTC · model grok-4.3

classification 🧮 math.CO

keywords K5-free graphsbipartite deletionRamsey-Turán theoryflag algebrasextremal graph theoryindependence numberTurán theoremedge-weighted graphs

0 comments

The pith

Every K5-free n-vertex graph with sublinear independence number can be made bipartite by removing at most n²(1/18+o(1)) edges.

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

The paper proves that every K5-free graph on n vertices whose largest independent set has size o(n) can be turned bipartite by deleting at most (1/18 + o(1)) n² edges. The constant 1/18 is shown to be asymptotically tight. The argument extends classical Turán theorems by moving to an edge-weighted setting where the goal is to maximize the size of a bipartite subgraph. The proof combines weighted Turán extensions with flag-algebra calculations. A sympathetic reader cares because the result gives a precise structural guarantee on how close such graphs are to being bipartite.

Core claim

We prove that every K_5-free n-vertex graph with sublinear independence number can be made bipartite by removing at most n^2(1/18+o(1)) edges, where the constant 1/18 is best possible. The proof method is related to extensions of Turán Theorem in edge-weighted settings, and part of the proof uses flag algebra.

What carries the argument

flag algebra methods applied to weighted Turán extensions

If this is right

The constant 1/18 is asymptotically optimal.
The bipartite deletion number is at most (1/18 + o(1))n² for every graph in this class.
Flag algebras yield the exact constant when applied to the corresponding weighted extremal problem.

Where Pith is reading between the lines

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

The same weighted-flag-algebra approach may produce sharp constants for other cut problems inside Ramsey-Turán classes.
K5-freeness plus o(n) independence number forces the existence of a bipartite subgraph larger than what ordinary Turán theory supplies.
One could check whether the 1/18 bound remains valid when the independence number is bounded by any fixed power n^ε.

Load-bearing premise

K5-freeness combined with sublinear independence number is enough for flag-algebra calculations on weighted Turán extensions to produce the sharp constant 1/18.

What would settle it

A K5-free graph with independence number o(n) whose minimum number of edges to delete to reach a bipartite graph exceeds n²/18 + o(n²), or an explicit construction that fails to meet the lower bound of n²/18.

read the original abstract

We prove that every $K_5$-free $n$-vertex graph with sublinear independence number can be made bipartite by removing at most $n^2(1/18+o(1))$ edges, where the constant $1/18$ is best possible. The proof method is related to extensions of Tur\'an Theorem in edge-weighted settings, and part of the proof uses flag algebra.

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.

Desk Editor's Note private letter to a colleague

The paper pins down a sharp 1/18 constant for the minimum edges to delete to make a K5-free graph with o(n) independence number bipartite.

read the letter

The main takeaway is that every K5-free n-vertex graph with independence number o(n) can be made bipartite by removing at most (1/18 + o(1))n² edges, and the constant is tight via a matching construction.

The work combines weighted Turán extensions with flag algebras to obtain the upper bound. This is new for the specific setting: the constant 1/18 does not follow from earlier published results on related deletion or Ramsey-Turán problems. The authors also supply an independent lower-bound construction, which keeps the argument from being circular.

The flag-algebra step is the part that delivers the exact constant, and the abstract presents the proof as complete. That is the main strength.

The soft spot is the computational certificate for the SDP. The stress-test note correctly flags that no explicit flag set, dimension, or rational certificate is mentioned in the abstract, so the precise tightness under the o(n) independence-number constraint is not immediately verifiable from the summary alone. If the full paper supplies the details and the numerical optimum really is 1/18 rather than slightly larger, the issue is minor; otherwise the o(1) term could mask a small gap.

This is a specialized result for people working on Ramsey-Turán problems and extremal deletion questions. A reader already familiar with flag-algebra techniques will get the most out of it. The paper deserves a serious referee because the claim is concrete, the method is standard for the area, and the lower-bound construction is independent.

Referee Report

2 major / 1 minor

Summary. The paper proves that every K_5-free n-vertex graph with independence number o(n) can be made bipartite by deleting at most (1/18 + o(1))n² edges, with the constant 1/18 shown to be best possible. The argument combines weighted Turán-type extensions with flag-algebra methods to obtain the upper bound.

Significance. If the flag-algebra calculation is correct, the result gives a sharp Ramsey-Turán style bound on the bipartite deletion number under the joint hypotheses of K_5-freeness and sublinear independence number. The use of weighted extensions to reduce the problem to an SDP whose optimum is claimed to be exactly 1/18 is a technically interesting approach.

major comments (2)

[flag-algebra portion of the proof] The flag-algebra argument (the portion of the proof that invokes flag algebras to obtain the weighted Turán bound) asserts that the associated SDP attains the exact value 1/18 under the α(G)=o(n) constraint, yet supplies neither the concrete flag set, the dimension of the SDP, the floating-point precision employed, nor a rational certificate establishing that the numerical optimum is attained at 1/18 rather than a slightly larger number. This gap directly affects the claimed sharpness of the constant.
[lower-bound section] The lower-bound construction establishing that 1/18 is best possible is stated to be independent of the upper-bound SDP, but the manuscript provides no explicit description of the construction or verification that it satisfies both K_5-freeness and α=o(n) while achieving deletion density (1/18 - o(1)).

minor comments (1)

The abstract and introduction could more explicitly state how the weighted Turán extensions interact with the flag-algebra SDP to enforce the α=o(n) condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the two major comments point by point below.

read point-by-point responses

Referee: [flag-algebra portion of the proof] The flag-algebra argument (the portion of the proof that invokes flag algebras to obtain the weighted Turán bound) asserts that the associated SDP attains the exact value 1/18 under the α(G)=o(n) constraint, yet supplies neither the concrete flag set, the dimension of the SDP, the floating-point precision employed, nor a rational certificate establishing that the numerical optimum is attained at 1/18 rather than a slightly larger number. This gap directly affects the claimed sharpness of the constant.

Authors: We agree that the manuscript does not supply the requested computational details. In the revised version we will include the concrete flag set, the dimension of the SDP, the floating-point precision employed, and a rational certificate (or exact algebraic verification) confirming that the numerical optimum equals exactly 1/18. revision: yes
Referee: [lower-bound section] The lower-bound construction establishing that 1/18 is best possible is stated to be independent of the upper-bound SDP, but the manuscript provides no explicit description of the construction or verification that it satisfies both K_5-freeness and α=o(n) while achieving deletion density (1/18 - o(1)).

Authors: We acknowledge that the manuscript omits an explicit description and verification of the lower-bound construction. In the revised version we will add a complete description of the construction together with proofs that it is K_5-free, has sublinear independence number, and attains deletion density (1/18 - o(1)). revision: yes

Circularity Check

0 steps flagged

No circularity: derivation relies on independent flag-algebra computation and separate lower-bound construction.

full rationale

The paper claims an upper bound of (1/18 + o(1))n² via weighted Turán extensions and flag algebras, with 1/18 shown best possible by a separate construction. No quoted step defines the target constant in terms of itself, renames a fitted parameter as a prediction, or reduces the central result to a self-citation chain. The flag-algebra SDP is presented as an external computational tool whose numerical output is asserted to match 1/18; this is not equivalent to the input by construction under the listed circularity patterns. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. The central claim rests on the domain assumption that K5-freeness plus sublinear independence number permits flag-algebra certification of the weighted Turán density 1/18.

axioms (1)

domain assumption K5-freeness and α(G)=o(n) suffice for the flag-algebra method to certify the extremal density 1/18
Invoked implicitly by the statement that the constant is best possible via flag algebras.

pith-pipeline@v0.9.1-grok · 5585 in / 1278 out tokens · 32916 ms · 2026-06-26T16:40:01.957337+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 19 canonical work pages

[1]

Weighted Tur´ an theorems with applications to Ramsey-Tur´ an type of problems.Journal of Graph Theory, 110(1):59– 71, 2025.doi:10.1002/jgt.23244

J´ ozsef Balogh, Domagoj Bradaˇ c, and Bernard Lidick´ y. Weighted Tur´ an theorems with applications to Ramsey-Tur´ an type of problems.Journal of Graph Theory, 110(1):59– 71, 2025.doi:10.1002/jgt.23244

work page doi:10.1002/jgt.23244 2025
[2]

Ramsey–Tur´ an problems with small independence numbers.European Journal of Combinatorics, 118:103872, 2024.doi:10.1016/j.ejc.2023.103872

J´ ozsef Balogh, Ce Chen, Grace McCourt, and Cassie Murley. Ramsey–Tur´ an problems with small independence numbers.European Journal of Combinatorics, 118:103872, 2024.doi:10.1016/j.ejc.2023.103872

work page doi:10.1016/j.ejc.2023.103872 2024
[3]

Max cuts in triangle-free graphs

J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lidick´ y. Max cuts in triangle-free graphs. InExtended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications, pages 509–514. Springer, 2021

2021
[4]

On two problems in Ramsey– Tur´ an theory.SIAM Journal on Discrete Mathematics, 31(3):1848–1866, 2017.doi: 10.1137/16M108607

J´ ozsef Balogh, Hong Liu, and Maryam Sharifzadeh. On two problems in Ramsey– Tur´ an theory.SIAM Journal on Discrete Mathematics, 31(3):1848–1866, 2017.doi: 10.1137/16M108607

work page doi:10.1137/16m108607 2017
[5]

Balanced bipartite distance ofK 4-free graphs, 2026.arXiv:2605.05346

J´ ozsef Balogh, Ignacy Buczek, Andrzej Grzesik, and Piotr Kuc. Balanced bipartite distance ofK 4-free graphs, 2026.arXiv:2605.05346

Pith/arXiv arXiv 2026
[6]

10 problems for partitions of triangle-free graphs.European Journal of Combinatorics, 121:103841, October 2024

J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lidick´ y. 10 problems for partitions of triangle-free graphs.European Journal of Combinatorics, 121:103841, October 2024. doi:10.1016/j.ejc.2023.103841

work page doi:10.1016/j.ejc.2023.103841 2024
[7]

Generalized Ramsey–Tur´ an numbers, 2024.arXiv:2405.01804

J´ ozsef Balogh, Van Magnan, and Cory Palmer. Generalized Ramsey–Tur´ an numbers, 2024.arXiv:2405.01804

arXiv 2024
[8]

Triangle- 11 tilings in graphs without large independent sets.Combinatorics, Probability and Com- puting, 27(4):449–474, 2018.doi:10.1017/S0963548318000196

J´ ozsef Balogh, Andrew McDowell, Theodore Molla, and Richard Mycroft. Triangle- 11 tilings in graphs without large independent sets.Combinatorics, Probability and Com- puting, 27(4):449–474, 2018.doi:10.1017/S0963548318000196

work page doi:10.1017/s0963548318000196 2018
[9]

Triangle factors of graphs without large independent sets and of weighted graphs.Random Structures & Algo- rithms, 49(4):669–693, 2016.doi:10.1002/rsa.20670

J´ ozsef Balogh, Theodore Molla, and Maryam Sharifzadeh. Triangle factors of graphs without large independent sets and of weighted graphs.Random Structures & Algo- rithms, 49(4):669–693, 2016.doi:10.1002/rsa.20670

work page doi:10.1002/rsa.20670 2016
[10]

On a Ramsey-Tur´ an type problem.J

B´ ela Bollob´ as and Paul Erd˝ os. On a Ramsey-Tur´ an type problem.J. Combinatorial Theory Ser. B, 21(2):166–168, 1976.doi:10.1016/0095-8956(76)90057-5

work page doi:10.1016/0095-8956(76)90057-5 1976
[11]

Problems and results in graph theory and combinatorial analysis

Paul Erd˝ os. Problems and results in graph theory and combinatorial analysis. In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), volume No. XV ofCongress. Numer., pages 169–192. Utilitas Math., Winnipeg, MB, 1976

1975
[12]

S´ os, and Endre Szemer´ edi

Paul Erd˝ os, Andr´ as Hajnal, Mikl´ os Simonovits, Vera T. S´ os, and Endre Szemer´ edi. Tur´ an-Ramsey theorems andKp-independence numbers.Combin. Probab. Comput., 3(3):297–325, 1994.doi:10.1017/S0963548300001218

work page doi:10.1017/s0963548300001218 1994
[13]

Paul Erd˝ os and Vera T. S´ os. Some remarks on Ramsey’s and Tur´ an’s theorem. In Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ ured, 1969), pages 395–404. North-Holland, Amsterdam, 1970

1969
[14]

Some old and new problems in various branches of combinatorics

Paul Erd˝ os. Some old and new problems in various branches of combinatorics. In Proceedings of an international symposium on Graphs and combinatorics, pages 227– 231, 1997.doi:10.1016/S0012-365X(96)00173-2

work page doi:10.1016/s0012-365x(96)00173-2 1997
[15]

Paul Erd˝ os, Ralph J Faudree, J´ anos Pach, and Joel H. Spencer. How to make a graph bi- partite.J. Comb. Theory B, 45(1):86–98, 1988.doi:10.1016/0095-8956(88)90057-3

work page doi:10.1016/0095-8956(88)90057-3 1988
[16]

Generalized Ramsey–Tur´ an den- sity for cliques

Jun Gao, Suyun Jiang, Hong Liu, and Maya Sankar. Generalized Ramsey–Tur´ an den- sity for cliques. InForum of Mathematics, Sigma, volume 13, page e78. Cambridge University Press, 2025.doi:10.1017/fms.2025.29

work page doi:10.1017/fms.2025.29 2025
[17]

A Ramsey–Tur´ an theory for tilings in graphs.Random Structures & Algorithms, 64(1):94–124, 2023.doi:10

Jie Han, Patrick Morris, Guanghui Wang, and Donglei Yang. A Ramsey–Tur´ an theory for tilings in graphs.Random Structures & Algorithms, 64(1):94–124, 2023.doi:10. 1002/rsa.21182

2023
[18]

Large multipar- tite subgraphs inH-free graphs

Ping Hu, Bernard Lidick´ y, Ta´ ısa Martins, Sergey Norin, and Jan Volec. Large multipar- tite subgraphs inH-free graphs. In Jaroslav Neˇ setˇ ril, Guillem Perarnau, Juanjo Ru´ e, and Oriol Serra, editors,Extended Abstracts EuroComb 2021, pages 707–713, Cham,

2021
[19]

Springer International Publishing
[20]

Two conjectures in Ramsey-Tur´ an theory

Jaehoon Kim, Younjin Kim, and Hong Liu. Two conjectures in Ramsey-Tur´ an theory. SIAM J. Discrete Math., 33(1):564–586, 2019.doi:10.1137/18M1186708

work page doi:10.1137/18m1186708 2019
[21]

Geometric constructions for Ramsey–Tur´ an theory.Journal of the European Mathematical Society: JEMS., 28(1):79, 2026.doi:10.4171/jems/1712

Hong Liu, Christian Reiher, Maryam Sharifzadeh, and Katherine Staden. Geometric constructions for Ramsey–Tur´ an theory.Journal of the European Mathematical Society: JEMS., 28(1):79, 2026.doi:10.4171/jems/1712

work page doi:10.4171/jems/1712 2026
[22]

Sparse halves inK 4-free graphs.Journal of Graph Theory, 99(1):5–25, 2021.doi:10.1002/jgt.22722

Xizhi Liu and Jie Ma. Sparse halves inK 4-free graphs.Journal of Graph Theory, 99(1):5–25, 2021.doi:10.1002/jgt.22722. 12

work page doi:10.1002/jgt.22722 2021
[23]

and Pehova, Y

Rajko Nenadov and Yanitsa Pehova. On a Ramsey–Tur´ an variant of the Hajnal– Szemer´ edi theorem.SIAM Journal on Discrete Mathematics, 34(2):1001–1010, 2020. doi:10.1137/18M1211970

work page doi:10.1137/18m1211970 2020
[24]

Razborov

Alexander A. Razborov. Flag algebras.J. Symbolic Logic, 72(4):1239–1282, 2007. doi:10.2178/jsl/1203350785

work page doi:10.2178/jsl/1203350785 2007
[25]

Razborov

Alexander A. Razborov. More about sparse halves in triangle-free graphs.Sbornik: Mathematics, 213(1):109–128, 2022.doi:10.1070/sm9615

work page doi:10.1070/sm9615 2022
[26]

Christian Reiher.K 4-free graphs have sparse halves.Bulletin of the London Mathemat- ical Society, 55(3):1178–1195, December 2022.doi:10.1112/blms.12782

work page doi:10.1112/blms.12782 2022
[27]

Vera T. S´ os. On extremal problems in graph theory. InCombinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 407–410. Gordon and Breach, New York, 1970

1969
[28]

Making aK 4-free graph bipartite.Combinatorica, 27(4):509–518, 2007

Benny Sudakov. Making aK 4-free graph bipartite.Combinatorica, 27(4):509–518, 2007. doi:10.1007/s00493-007-2238-0

work page doi:10.1007/s00493-007-2238-0 2007
[29]

On graphs containing no complete subgraph with 4 vertices.Mat

Endre Szemer´ edi. On graphs containing no complete subgraph with 4 vertices.Mat. Lapok, 23:113–116 (1973), 1972. Appendix The purpose of this Appendix is to describe a strengthening of Lemma 4.1 by proving a stability version. The complete balanced tripartite graph with every edge having weight 1/2 requires a cut of weightn 2/18. As this graph has no hea...

1973

[1] [1]

Weighted Tur´ an theorems with applications to Ramsey-Tur´ an type of problems.Journal of Graph Theory, 110(1):59– 71, 2025.doi:10.1002/jgt.23244

J´ ozsef Balogh, Domagoj Bradaˇ c, and Bernard Lidick´ y. Weighted Tur´ an theorems with applications to Ramsey-Tur´ an type of problems.Journal of Graph Theory, 110(1):59– 71, 2025.doi:10.1002/jgt.23244

work page doi:10.1002/jgt.23244 2025

[2] [2]

Ramsey–Tur´ an problems with small independence numbers.European Journal of Combinatorics, 118:103872, 2024.doi:10.1016/j.ejc.2023.103872

J´ ozsef Balogh, Ce Chen, Grace McCourt, and Cassie Murley. Ramsey–Tur´ an problems with small independence numbers.European Journal of Combinatorics, 118:103872, 2024.doi:10.1016/j.ejc.2023.103872

work page doi:10.1016/j.ejc.2023.103872 2024

[3] [3]

Max cuts in triangle-free graphs

J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lidick´ y. Max cuts in triangle-free graphs. InExtended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications, pages 509–514. Springer, 2021

2021

[4] [4]

On two problems in Ramsey– Tur´ an theory.SIAM Journal on Discrete Mathematics, 31(3):1848–1866, 2017.doi: 10.1137/16M108607

J´ ozsef Balogh, Hong Liu, and Maryam Sharifzadeh. On two problems in Ramsey– Tur´ an theory.SIAM Journal on Discrete Mathematics, 31(3):1848–1866, 2017.doi: 10.1137/16M108607

work page doi:10.1137/16m108607 2017

[5] [5]

Balanced bipartite distance ofK 4-free graphs, 2026.arXiv:2605.05346

J´ ozsef Balogh, Ignacy Buczek, Andrzej Grzesik, and Piotr Kuc. Balanced bipartite distance ofK 4-free graphs, 2026.arXiv:2605.05346

Pith/arXiv arXiv 2026

[6] [6]

10 problems for partitions of triangle-free graphs.European Journal of Combinatorics, 121:103841, October 2024

J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lidick´ y. 10 problems for partitions of triangle-free graphs.European Journal of Combinatorics, 121:103841, October 2024. doi:10.1016/j.ejc.2023.103841

work page doi:10.1016/j.ejc.2023.103841 2024

[7] [7]

Generalized Ramsey–Tur´ an numbers, 2024.arXiv:2405.01804

J´ ozsef Balogh, Van Magnan, and Cory Palmer. Generalized Ramsey–Tur´ an numbers, 2024.arXiv:2405.01804

arXiv 2024

[8] [8]

Triangle- 11 tilings in graphs without large independent sets.Combinatorics, Probability and Com- puting, 27(4):449–474, 2018.doi:10.1017/S0963548318000196

J´ ozsef Balogh, Andrew McDowell, Theodore Molla, and Richard Mycroft. Triangle- 11 tilings in graphs without large independent sets.Combinatorics, Probability and Com- puting, 27(4):449–474, 2018.doi:10.1017/S0963548318000196

work page doi:10.1017/s0963548318000196 2018

[9] [9]

Triangle factors of graphs without large independent sets and of weighted graphs.Random Structures & Algo- rithms, 49(4):669–693, 2016.doi:10.1002/rsa.20670

J´ ozsef Balogh, Theodore Molla, and Maryam Sharifzadeh. Triangle factors of graphs without large independent sets and of weighted graphs.Random Structures & Algo- rithms, 49(4):669–693, 2016.doi:10.1002/rsa.20670

work page doi:10.1002/rsa.20670 2016

[10] [10]

On a Ramsey-Tur´ an type problem.J

B´ ela Bollob´ as and Paul Erd˝ os. On a Ramsey-Tur´ an type problem.J. Combinatorial Theory Ser. B, 21(2):166–168, 1976.doi:10.1016/0095-8956(76)90057-5

work page doi:10.1016/0095-8956(76)90057-5 1976

[11] [11]

Problems and results in graph theory and combinatorial analysis

Paul Erd˝ os. Problems and results in graph theory and combinatorial analysis. In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), volume No. XV ofCongress. Numer., pages 169–192. Utilitas Math., Winnipeg, MB, 1976

1975

[12] [12]

S´ os, and Endre Szemer´ edi

Paul Erd˝ os, Andr´ as Hajnal, Mikl´ os Simonovits, Vera T. S´ os, and Endre Szemer´ edi. Tur´ an-Ramsey theorems andKp-independence numbers.Combin. Probab. Comput., 3(3):297–325, 1994.doi:10.1017/S0963548300001218

work page doi:10.1017/s0963548300001218 1994

[13] [13]

Paul Erd˝ os and Vera T. S´ os. Some remarks on Ramsey’s and Tur´ an’s theorem. In Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ ured, 1969), pages 395–404. North-Holland, Amsterdam, 1970

1969

[14] [14]

Some old and new problems in various branches of combinatorics

Paul Erd˝ os. Some old and new problems in various branches of combinatorics. In Proceedings of an international symposium on Graphs and combinatorics, pages 227– 231, 1997.doi:10.1016/S0012-365X(96)00173-2

work page doi:10.1016/s0012-365x(96)00173-2 1997

[15] [15]

Paul Erd˝ os, Ralph J Faudree, J´ anos Pach, and Joel H. Spencer. How to make a graph bi- partite.J. Comb. Theory B, 45(1):86–98, 1988.doi:10.1016/0095-8956(88)90057-3

work page doi:10.1016/0095-8956(88)90057-3 1988

[16] [16]

Generalized Ramsey–Tur´ an den- sity for cliques

Jun Gao, Suyun Jiang, Hong Liu, and Maya Sankar. Generalized Ramsey–Tur´ an den- sity for cliques. InForum of Mathematics, Sigma, volume 13, page e78. Cambridge University Press, 2025.doi:10.1017/fms.2025.29

work page doi:10.1017/fms.2025.29 2025

[17] [17]

A Ramsey–Tur´ an theory for tilings in graphs.Random Structures & Algorithms, 64(1):94–124, 2023.doi:10

Jie Han, Patrick Morris, Guanghui Wang, and Donglei Yang. A Ramsey–Tur´ an theory for tilings in graphs.Random Structures & Algorithms, 64(1):94–124, 2023.doi:10. 1002/rsa.21182

2023

[18] [18]

Large multipar- tite subgraphs inH-free graphs

Ping Hu, Bernard Lidick´ y, Ta´ ısa Martins, Sergey Norin, and Jan Volec. Large multipar- tite subgraphs inH-free graphs. In Jaroslav Neˇ setˇ ril, Guillem Perarnau, Juanjo Ru´ e, and Oriol Serra, editors,Extended Abstracts EuroComb 2021, pages 707–713, Cham,

2021

[19] [19]

Springer International Publishing

[20] [20]

Two conjectures in Ramsey-Tur´ an theory

Jaehoon Kim, Younjin Kim, and Hong Liu. Two conjectures in Ramsey-Tur´ an theory. SIAM J. Discrete Math., 33(1):564–586, 2019.doi:10.1137/18M1186708

work page doi:10.1137/18m1186708 2019

[21] [21]

Geometric constructions for Ramsey–Tur´ an theory.Journal of the European Mathematical Society: JEMS., 28(1):79, 2026.doi:10.4171/jems/1712

Hong Liu, Christian Reiher, Maryam Sharifzadeh, and Katherine Staden. Geometric constructions for Ramsey–Tur´ an theory.Journal of the European Mathematical Society: JEMS., 28(1):79, 2026.doi:10.4171/jems/1712

work page doi:10.4171/jems/1712 2026

[22] [22]

Sparse halves inK 4-free graphs.Journal of Graph Theory, 99(1):5–25, 2021.doi:10.1002/jgt.22722

Xizhi Liu and Jie Ma. Sparse halves inK 4-free graphs.Journal of Graph Theory, 99(1):5–25, 2021.doi:10.1002/jgt.22722. 12

work page doi:10.1002/jgt.22722 2021

[23] [23]

and Pehova, Y

Rajko Nenadov and Yanitsa Pehova. On a Ramsey–Tur´ an variant of the Hajnal– Szemer´ edi theorem.SIAM Journal on Discrete Mathematics, 34(2):1001–1010, 2020. doi:10.1137/18M1211970

work page doi:10.1137/18m1211970 2020

[24] [24]

Razborov

Alexander A. Razborov. Flag algebras.J. Symbolic Logic, 72(4):1239–1282, 2007. doi:10.2178/jsl/1203350785

work page doi:10.2178/jsl/1203350785 2007

[25] [25]

Razborov

Alexander A. Razborov. More about sparse halves in triangle-free graphs.Sbornik: Mathematics, 213(1):109–128, 2022.doi:10.1070/sm9615

work page doi:10.1070/sm9615 2022

[26] [26]

Christian Reiher.K 4-free graphs have sparse halves.Bulletin of the London Mathemat- ical Society, 55(3):1178–1195, December 2022.doi:10.1112/blms.12782

work page doi:10.1112/blms.12782 2022

[27] [27]

Vera T. S´ os. On extremal problems in graph theory. InCombinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 407–410. Gordon and Breach, New York, 1970

1969

[28] [28]

Making aK 4-free graph bipartite.Combinatorica, 27(4):509–518, 2007

Benny Sudakov. Making aK 4-free graph bipartite.Combinatorica, 27(4):509–518, 2007. doi:10.1007/s00493-007-2238-0

work page doi:10.1007/s00493-007-2238-0 2007

[29] [29]

On graphs containing no complete subgraph with 4 vertices.Mat

Endre Szemer´ edi. On graphs containing no complete subgraph with 4 vertices.Mat. Lapok, 23:113–116 (1973), 1972. Appendix The purpose of this Appendix is to describe a strengthening of Lemma 4.1 by proving a stability version. The complete balanced tripartite graph with every edge having weight 1/2 requires a cut of weightn 2/18. As this graph has no hea...

1973