betaFeedback

WorksMathematics

Seeking the dense half in K4K_4-free graphs

Abstract

We show that every K4K_4-free graph on nn vertices has a balanced bipartition such that neither part contains more than 0.0671n2+o(n2)0.0671n^2 + o(n^2) edges. This improves the previous best bound of 0.074n20.074n^2 by Xu and Zhang. We also formulate a conjecture that the tight bound for this problem is 4256498n2≈0.0654n2\frac{425}{6498}n^2 \approx 0.0654n^2, and present a construction showing that it would be best possible.

Introduction

The Sparse half conjecture of Erdős ([6]) states that in a triangle-free graph on nn vertices one can always find a vertex subset of size at least n2\frac{n}{2} such that at most n250\frac{n^2}{50} edges have both of their endpoints in it. This conjecture has received a lot of attention ([13, 15, 8, 11]). The best bound so far is 27n21024\frac{27n^2}{1024}, and it was achieved by Razborov in [15].

A related conjecture of Erdős is that every triangle-free graph on nn vertices can be made bipartite by removing at most n225\frac{n^2}{25} edges. This question has also been extensively studied over the years ([7, 9, 3]), and the best known bound of 2n247\frac{2n^2}{47} was proven in [3].

Recently, Balogh, Clemen and Lidický ([2]) have proposed a number of problems on finding partitions with few edges inside the parts. Many of these focus on balanced kk-partitions, partly because a good balanced bipartition yields a sparse half. We recall that a kk-partition V(G)=A1∪…∪AkV(G)=A_1\cup\ldots\cup A_k is balanced if ∣∣Ai∣−∣Aj∣∣≤1\lvert\lvert A_i\rvert-\lvert A_j\rvert\rvert\le1 for all i,j∈{1,…,k}i,j\in\{1,\ldots,k\}. Let

Dkb(G)=min⁡A1,…,Ak∑i=1ke(Ai),(1)D_k^b(G)=\min_{A_1,\ldots,A_k}\sum_{i=1}^{k}e(A_i), \tag*{(1)}

where the minimum is taken over all balanced kk-partitions and e(Ai)e(A_i) denotes the number of edges with both endpoints in AiA_i. It turns out that proving tight bounds for small values of kk in the class of triangle-free graphs is easier than resolving the original conjectures of Erdős.

Theorem 1.1 ([2]). If GG is a sufficiently large triangle-free graph on nn vertices, then

D2b(G)≤n216andD3b(G)≤n236.D_2^b(G)\le\frac{n^2}{16}\qquad\text{and}\qquad D_3^b(G)\le\frac{n^2}{36}.

Moreover, D2b(K3n4,n4)=n216D_2^b\left(K_{\frac{3n}{4},\frac{n}{4}}\right)=\frac{n^2}{16} and D3b(Kn2,n2)=n236D_3^b\left(K_{\frac{n}{2},\frac{n}{2}}\right)=\frac{n^2}{36}.

The authors of [2] also considered such problems in the class of K4K_4-free graphs and formulated a conjecture on the optimal bound for D2bD^b_2. This conjecture was recently proved by Balogh and the authors of this paper.

Theorem 1.2 ([1]). If GG is a K4K_4-free graph on nn vertices, then

D2b(G)≤n29.D^b_2(G) \le\frac{n^2}{9}.

Moreover, D2b(Kn3,n3,n3)=n29D^b_2(K_{\frac{n}{3},\frac{n}{3},\frac{n}{3}}) = \frac{n^2}{9}.

A natural way of generalizing (1) is by considering the ℓp\ell_p-norm of the vector (e(Ai))i(e(A_i))_i, rather than a simple sum. Formally, let

Dk,pb(G)=min⁡A1,…,Ak∥(e(Ai))i∥p,D^b_{k,p}(G) = \min_{A_1,\ldots,A_k} \lVert(e(A_i))_i\rVert_p,

where the minimum is taken over all balanced kk-partitions of GG. Note that Dk,1b=DkbD^b_{k,1}=D^b_k, and Dk,∞b(G)=min⁡A1,…,Akmax⁡ie(Ai)D^b_{k,\infty}(G)=\min_{A_1,\ldots,A_k}\max_i e(A_i). The only parameter that has received some attention aside from Dk,1bD^b_{k,1} is Dk,∞bD^b_{k,\infty}, as other cases seem to be outside the reach of the currently known methodology. Intuitively, the problem of determining Dk,∞bD^b_{k,\infty} amounts to finding a balanced kk-partition in which the densest part spans as few edges as possible.

Theorem 1.3 ([2]). If GG is a triangle-free graph on nn vertices, then

D2,∞b(G)≤n218andD3,∞b(G)≤n248+o(n2).D^b_{2,\infty}(G) \le\frac{n^2}{18} \qquad\text{and}\qquad D^b_{3,\infty}(G) \le\frac{n^2}{48}+o(n^2).

Moreover, D2,∞b(K2n3,n3)=n218D^b_{2,\infty}(K_{\frac{2n}{3},\frac{n}{3}})=\frac{n^2}{18} and D3,∞b(Kn2,n2)=n248D^b_{3,\infty}(K_{\frac{n}{2},\frac{n}{2}})=\frac{n^2}{48}.

Interestingly, it seems as if proving tight bounds on Dk,∞bD^b_{k,\infty} in the class of K4K_4-free graphs is noticeably more difficult, despite early optimistic conjectures.

Conjecture 1.4 ([2]). If GG is a K4K_4-free graph on nn vertices, then

D2,∞b(G)≤n216.D^b_{2,\infty}(G) \le\frac{n^2}{16}.

Theorem 1.4 was quickly disproven by Xu and Zhang in [16].

Theorem 1.5 ([16]). There exists an infinite family of K4K_4-free graphs such that every graph GG in this family satisfies

D2,∞b(G)=37242∣G∣2≈0.0642⋅∣G∣2>0.0625⋅∣G∣2=∣G∣216.D^b_{2,\infty}(G)=\frac{37}{24^2}|G|^2\approx0.0642\cdot|G|^2>0.0625\cdot|G|^2=\frac{|G|^2}{16}.

Another important observation made in [16] is that it seems difficult to obtain even relatively weak upper bounds on D2,∞bD^b_{2,\infty} in the class of K4K_4-free graphs.

Theorem 1.6 ([16]). If GG is a K4K_4-free graph on n>105n>10^5 vertices, then

D2,∞b(G)≤0.074n2.D^b_{2,\infty}(G)\le0.074n^2.

In this work, we examine more closely the most relevant constructions for extremal values of D2,∞bD^b_{2,\infty} in the class of K4K_4-free graphs and employ more advanced techniques to significantly narrow the gap between the bounds in Theorem 1.5 and Theorem 1.6, from 0.0098 to below 0.0017. First, we show a family of graphs which gives an even better lower bound.

Theorem 1.7. There exists an infinite family of K4K_4-free graphs, such that every graph GG in this family satisfies

D2,∞b(G)=4256498∣G∣2≈0.0654⋅∣G∣2.D^b_{2,\infty}(G)=\frac{425}{6498}|G|^2\approx0.0654\cdot|G|^2.

Afterwards, using our improved understanding of potential extremal constructions, we leverage flag algebras to obtain a significantly better upper bound.

Theorem 1.8. If GG is a K4K_4-free graph on nn vertices, then

D2,∞b(G)≤0.0671n2+5n53.D^b_{2,\infty}(G)\leq0.0671n^2+5n^{\frac{5}{3}}.

Lower bound

Before we describe the family of graphs proving Theorem 1.7, we recall some useful notions and a technical lemma from [16]. An nn-blowup of a graph GG is a graph obtained by replacing every vertex in GG with nn copies. Vertices in the blowup are connected if and only if their original counterparts in GG are connected.

Lemma 2.1 ([16]). If FF is an induced subgraph of order pn+qpn+q of the nn-blowup of C5C_5, where pp and qq are non-negative integers with p<5p<5 and q<nq<n, then

e(F)≥f(n,p,q):={0,if p≤1,qn,if p=2,n2+2qn,if p=3,3n2+2qn,if p=4.e(F)\geq f(n,p,q):= \begin{cases} 0, & \text{if }p\leq1,\\ qn, & \text{if }p=2,\\ n^2+2qn, & \text{if }p=3,\\ 3n^2+2qn, & \text{if }p=4. \end{cases}

References

  1. [1]József Balogh, Ignacy Buczek, Andrzej Grzesik, and Piotr Kuc. Balanced bipartite distance of K₄-free graphs. 2026. arXiv: 2605.05346.arxiv.org/abs/2605.05346
  2. [2]József Balogh, Felix Christian Clemen, and Bernard Lidický. “10 problems for partitions of triangle-free graphs”. In: European Journal of Combinatorics 121 (2024), p. 103841.arxiv.org/abs/2203.15764
  3. [3]József Balogh, Felix Christian Clemen, and Bernard Lidický. “Max cuts in triangle-free graphs”. In: Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications. Springer. 2021, pp. 509–514.arxiv.org/abs/2103.14179
  4. [4]Brian Borchers. “CSDP, a C library for Semidefinite Programming”. In: Optimization Methods and Software 11 (1998), pp. 613–623.DOI
  5. [5]Dalton Burke, Bernard Lidický, Florian Pfender, and Michael Phillips. “Inducibility of Four-Vertex Tournaments”. In: Journal of Graph Theory 113.3 (2026), pp. 508–522.DOI
  6. [10]Ping Hu, Bernard Lidický, Taísa Martins, Sergey Norin, and Jan Volec. “Large Multipartite Subgraphs in H-free Graphs”. In: Extended Abstracts EuroComb 2021. Springer International Publishing, 2021, pp. 707–713.DOI
  7. [12]Choongbum Lee, Po-Shen Loh, and Benny Sudakov. “Bisections of graphs”. In: Journal of Combinatorial Theory, Series B 103.5 (2013), pp. 599–629.
  8. [14]Alexander Razborov. “Flag Algebras”. In: The Journal of Symbolic Logic 72.4 (2007), pp. 1239–1282.
  9. [15]Alexander Razborov. “More about sparse halves in triangle-free graphs”. In: Sbornik: Mathematics 213.1 (2022), pp. 109–128.DOI
  10. [16]Yue Xu and Xiao-Dong Zhang. Dense halves in balanced 2-partition of K₄-free graphs. 2024. arXiv: 2412.13485.arxiv.org/abs/2412.13485

Paper details

vlnc:W_sa6fr9e9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

large language models

View statement
Looking for related papers…
Contents