Balanced bipartite distance of K 4 K_{4} -free graphs

József Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc · 2026

Read Balanced bipartite distance of K 4 K_{4} -free graphs by József Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05346.txt.

Introduction

József Balogh and three co-authors prove a clean bound in graph theory. Start with a graph that contains no complete graph on four vertices. The question is how many edges must be deleted so the rest splits neatly into two balanced groups with edges only between them.

They show that removing at most one ninth of the square of the vertex count always suffices. That result proves a conjecture by Balogh, Clemen, and Lidický. It also extends two earlier results, one by Sudakov on bipartite distance and one by Reiher on the sparse half of such graphs.

Catalog record

CREATORJózsef Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE523 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05346

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Balanced bipartite distance of K 4 K_{4} -free graphs József Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc Abstract We show that every K 4 K_{4} -free graph on n n vertices can be made balanced bipartite by removing at most n 2 9 \frac{n^{2}}{9} edges. This proves a conjecture of Balogh, Clemen, and Lidický, and generalizes both Sudakov’s result on the bipartite distance of K 4 K_{4} -free graphs and Reiher’s result on the sparse half of K 4 K_{4} -free graphs. † † footnotemark: † † footnotetext: E-mails: [email protected] , [email protected] , [email protected] , [email protected] . 1 Introduction The famous Sparse half conjecture of Erdős [ 12 ] , open for over 50 years, states that every n -vertex triangle-free graph has a subset of vertices of size \frac{n}{2} that spans at most \frac{n^{2}}{50} edges. This conjecture received a lot of attention, see [ 9 , 19 , 22 , 28 ] , with Razborov achieving the strongest known general bound of \frac{27n^{2}}{1024} in [ 28 ] . A similar problem, the Sparse halves conjecture , which asks for the minimum number of edges that must be removed from a triangle-free graph to make it bipartite, was posed by Erdős [ 11 ] even earlier. This question is closely related to the Sparse half conjecture , as it is expected that the tight lower bounds for both problems are attained by the same extremal graph (a balanced blowup of a pentagon). Because of this, it is believed that to make a triangle-free graph bipartite, it is always sufficient to remove \frac{n^{2}}{50}\cdot 2=\frac{n^{2}}{25} edges. This problem is also difficult and has attracted considerable attention [ 2 , 8 , 10 ] . The best known general bound is \frac{2n^{2}}{47} , which was recently proved in [ 2 ] . It is important to note that there is no implication relationship between the Sparse half conjecture and the Sparse halves conjecture , which is why they gave rise to two relatively independent research directions. A pertinent question is that if these problems have an intuitive generalization, with a natural candidate being a hypothetical bound on the number of edges that have to be removed to make a triangle-free graph balanced bipartite. If the tight bound was identical to the Sparse halves conjecture and equaled \frac{n^{2}}{25} , it would imply both of the conjectures. This question was initially asked and answered by Balogh, Clemen, and Lidický in [ 3 ] , with the answer being unfortunately negative. It is easy to see that to make the complete bipartite graph with parts of sizes \frac{3n}{4} and \frac{n}{4} balanced bipartite, one always has to remove at least \frac{n^{2}}{16} edges. Balogh, Clemen, and Lidický ( [ 3 ] ) proved that this is the optimal bound in general. This implies that, surprisingly, proving a tight bound for this problem is significantly easier than for the unbalanced one. Theorem 1.1 (Balogh, Clemen, and Lidický [ 3 ] ) . Every triangle-free graph on n vertices can be made balanced bipartite by removing at most \frac{n^{2}}{16} edges. The motive of asking how far from being bipartite a graph can be is a recurring theme in Erdős’ work. Not long after asking this question for the class of triangle-free graphs, he [ 8 ] formulated a similar problem in the K_{4} -free setting, where he conjectured that the complete tripartite graph is the extremal example. This was proved by Sudakov [ 31 ] . Theorem 1.2 (Sudakov [ 31 ] ) . Every K_{4} -free graph on n vertices can be made bipartite by removing at most \frac{n^{2}}{9} edges. The Sparse half conjecture also has a natural variant for K_{4} -free graphs, see [ 8 ] , which was posed by Chung and Graham [ 7 ] and independently by Erdős, Faudree, Rousseau and Schelp [ 9 ] . Both groups anticipated that the tight bound should be once again attained by the complete balanced tripartite graph. Confirming this bound seemed more elusive than proving the tight bound on the bipartite distance, but building on the partial progress of Liu and Ma ( [ 21 ] ), who settled the conjecture for regular graphs, Reiher [ 29 ] recently managed to do so. Theorem 1.3 (Reiher [ 29 ] ) . Every K_{4} -free graph on n vertices has a subset of \frac{n}{2} vertices which spans at most \frac{n^{2}}{18} edges. Analogously to the Sparse half conjecture and the Sparse halves conjecture , Theorem 1.2 and Theorem 1.3 could be potentially generalized by a sufficiently strong bound on the balanced bipartite distance in the class of K_{4} -free graphs. Theorem 1.1 naturally suggests that such a bound is unlikely to be obtained. Intriguingly, Balogh, Clemen, and Lidický [ 3 ] noticed that the usual interesting candidates in the K_{4} -free class are not sufficient to exclude the possibility of such a bound, which led them to conjecture that it might actually be achievable. 1.4 Balogh, Clemen, and Lidický [ 3 ] . Every K_{4} -free graph on n vertices can be made balanced bipartite by removing at most \frac{n^{2}}{9} edges. In this work, we show that 1.4 holds. This directly generalizes, and gives a different proof of the aforementioned results of Sudakov ( [ 31 ] ) and Reiher ( [ 29 ] ). Moreover, it confirms an unexpected discrepancy between the classes of triangle-free and K_{4} -free graphs. The proof consists of two major steps. First, we show 1.4 for all graphs that are sufficiently close to the complete balanced tripartite graph. In the second step, we introduce an improved approach of describing graphs cuts in Razborov’s flag algebra framework ( [ 24 ] ) to show that a potential counterexample would need to be very close to the complete balanced tripartite graph, which is not possible due to the previously proven statement. It is worth noting that while the idea of combining flag algebras with graph cuts has been used in the literature ( [ 3 ] , [ 2 ] ), its usual application is not suitable for this problem or most partitioning problems that impose requirements on the sizes of the components in the partition. We overcome this obstacle by applying flag algebras to a vertex-colored graph derived from the potential counterexample, where colors of vertices encode extra information that gives more control of the partitions. We believe that this approach should be applicable to other partitioning problems and should lead to further progress on the Sparse half conjecture and Sparse half conjectures . The paper is organized as follows. In Section 2 we introduce basic graph notation used in the paper. Section 3 is devoted to proving some basic subcases of 1.4 that will be needed later. In Section 4 we include the proof of 1.4 for graphs that contain a large pair of independent sets. This result is used in Section 5 that solves the conjecture in the close neighborhood of the extremal example. To finish the proof in the general case, we use the flag algebra framework, which we briefly introduce in Section 6 . The proof of our main result is completed in Section 7 . 2 Notation For a graph

Read the complete text