Introduction
The Sparse half conjecture of Erdős ([6]) states that in a triangle-free graph on n n n vertices one can always find a vertex subset of size at least n 2 \frac{n}{2} 2 n such that at most n 2 50 \frac{n^2}{50} 50 n 2 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 27 n 2 1024 \frac{27n^2}{1024} 1024 27 n 2 , and it was achieved by Razborov in [15 ] .
A related conjecture of Erdős is that every triangle-free graph on n n n vertices can be made bipartite by removing at most n 2 25 \frac{n^2}{25} 25 n 2 edges. This question has also been extensively studied over the years ([7, 9, 3]), and the best known bound of 2 n 2 47 \frac{2n^2}{47} 47 2 n 2 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 k k k -partitions, partly because a good balanced bipartition yields a sparse half. We recall that a k k k -partition V ( G ) = A 1 ∪ … ∪ A k V(G)=A_1\cup\ldots\cup A_k V ( G ) = A 1 ∪ … ∪ A k is balanced if ∣ ∣ A i ∣ − ∣ A j ∣ ∣ ≤ 1 \lvert\lvert A_i\rvert-\lvert A_j\rvert\rvert\le1 ∣∣ A i ∣ − ∣ A j ∣∣ ≤ 1 for all i , j ∈ { 1 , … , k } i,j\in\{1,\ldots,k\} i , j ∈ { 1 , … , k } . Let
D k b ( G ) = min A 1 , … , A k ∑ i = 1 k e ( A i ) , (1) D_k^b(G)=\min_{A_1,\ldots,A_k}\sum_{i=1}^{k}e(A_i), \tag*{(1)} D k b ( G ) = A 1 , … , A k min i = 1 ∑ k e ( A i ) , (1)
where the minimum is taken over all balanced k k k -partitions and e ( A i ) e(A_i) e ( A i ) denotes the number of edges with both endpoints in A i A_i A i . It turns out that proving tight bounds for small values of k k k in the class of triangle-free graphs is easier than resolving the original conjectures of Erdős.
Theorem 1.1 ([2]). If G G G is a sufficiently large triangle-free graph on n n n vertices, then
D 2 b ( G ) ≤ n 2 16 and D 3 b ( G ) ≤ n 2 36 . D_2^b(G)\le\frac{n^2}{16}\qquad\text{and}\qquad D_3^b(G)\le\frac{n^2}{36}. D 2 b ( G ) ≤ 16 n 2 and D 3 b ( G ) ≤ 36 n 2 . Moreover, D 2 b ( K 3 n 4 , n 4 ) = n 2 16 D_2^b\left(K_{\frac{3n}{4},\frac{n}{4}}\right)=\frac{n^2}{16} D 2 b ( K 4 3 n , 4 n ) = 16 n 2 and D 3 b ( K n 2 , n 2 ) = n 2 36 D_3^b\left(K_{\frac{n}{2},\frac{n}{2}}\right)=\frac{n^2}{36} D 3 b ( K 2 n , 2 n ) = 36 n 2 .
The authors of [2 ] also considered such problems in the class of K 4 K_4 K 4 -free graphs and formulated a conjecture on the optimal bound for D 2 b D^b_2 D 2 b . This conjecture was recently proved by Balogh and the authors of this paper.
Theorem 1.2 ([1 ] ). If G G G is a K 4 K_4 K 4 -free graph on n n n vertices, then
D 2 b ( G ) ≤ n 2 9 . D^b_2(G) \le\frac{n^2}{9}. D 2 b ( G ) ≤ 9 n 2 . Moreover, D 2 b ( K n 3 , n 3 , n 3 ) = n 2 9 D^b_2(K_{\frac{n}{3},\frac{n}{3},\frac{n}{3}}) = \frac{n^2}{9} D 2 b ( K 3 n , 3 n , 3 n ) = 9 n 2 .
A natural way of generalizing (1) is by considering the ℓ p \ell_p ℓ p -norm of the vector ( e ( A i ) ) i (e(A_i))_i ( e ( A i ) ) i , rather than a simple sum. Formally, let
D k , p b ( G ) = min A 1 , … , A k ∥ ( e ( A i ) ) i ∥ p , D^b_{k,p}(G) = \min_{A_1,\ldots,A_k} \lVert(e(A_i))_i\rVert_p, D k , p b ( G ) = A 1 , … , A k min ∥( e ( A i ) ) i ∥ p ,
where the minimum is taken over all balanced k k k -partitions of G G G . Note that D k , 1 b = D k b D^b_{k,1}=D^b_k D k , 1 b = D k b , and D k , ∞ b ( G ) = min A 1 , … , A k max i e ( A i ) D^b_{k,\infty}(G)=\min_{A_1,\ldots,A_k}\max_i e(A_i) D k , ∞ b ( G ) = min A 1 , … , A k max i e ( A i ) . The only parameter that has received some attention aside from D k , 1 b D^b_{k,1} D k , 1 b is D k , ∞ b D^b_{k,\infty} D k , ∞ b , as other cases seem to be outside the reach of the currently known methodology. Intuitively, the problem of determining D k , ∞ b D^b_{k,\infty} D k , ∞ b amounts to finding a balanced k k k -partition in which the densest part spans as few edges as possible.
Theorem 1.3 ([2 ] ). If G G G is a triangle-free graph on n n n vertices, then
D 2 , ∞ b ( G ) ≤ n 2 18 and D 3 , ∞ b ( G ) ≤ n 2 48 + o ( n 2 ) . 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). D 2 , ∞ b ( G ) ≤ 18 n 2 and D 3 , ∞ b ( G ) ≤ 48 n 2 + o ( n 2 ) . Moreover, D 2 , ∞ b ( K 2 n 3 , n 3 ) = n 2 18 D^b_{2,\infty}(K_{\frac{2n}{3},\frac{n}{3}})=\frac{n^2}{18} D 2 , ∞ b ( K 3 2 n , 3 n ) = 18 n 2 and D 3 , ∞ b ( K n 2 , n 2 ) = n 2 48 D^b_{3,\infty}(K_{\frac{n}{2},\frac{n}{2}})=\frac{n^2}{48} D 3 , ∞ b ( K 2 n , 2 n ) = 48 n 2 .
Interestingly, it seems as if proving tight bounds on D k , ∞ b D^b_{k,\infty} D k , ∞ b in the class of K 4 K_4 K 4 -free graphs is noticeably more difficult, despite early optimistic conjectures.
Conjecture 1.4 ([2 ] ). If G G G is a K 4 K_4 K 4 -free graph on n n n vertices, then
D 2 , ∞ b ( G ) ≤ n 2 16 . D^b_{2,\infty}(G) \le\frac{n^2}{16}. D 2 , ∞ b ( G ) ≤ 16 n 2 .
Theorem 1.4 was quickly disproven by Xu and Zhang in [16 ] .
Theorem 1.5 ([16 ] ). There exists an infinite family of K 4 K_4 K 4 -free graphs such that every graph G G G in this family satisfies
D 2 , ∞ b ( G ) = 37 24 2 ∣ G ∣ 2 ≈ 0.0642 ⋅ ∣ G ∣ 2 > 0.0625 ⋅ ∣ G ∣ 2 = ∣ G ∣ 2 16 . 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}. D 2 , ∞ b ( G ) = 2 4 2 37 ∣ G ∣ 2 ≈ 0.0642 ⋅ ∣ G ∣ 2 > 0.0625 ⋅ ∣ G ∣ 2 = 16 ∣ G ∣ 2 .
Another important observation made in [16 ] is that it seems difficult to obtain even relatively weak upper bounds on D 2 , ∞ b D^b_{2,\infty} D 2 , ∞ b in the class of K 4 K_4 K 4 -free graphs.
Theorem 1.6 ([16 ] ). If G G G is a K 4 K_4 K 4 -free graph on n > 10 5 n>10^5 n > 1 0 5 vertices, then
D 2 , ∞ b ( G ) ≤ 0.074 n 2 . D^b_{2,\infty}(G)\le0.074n^2. D 2 , ∞ b ( G ) ≤ 0.074 n 2 .
In this work, we examine more closely the most relevant constructions for extremal values of D 2 , ∞ b D^b_{2,\infty} D 2 , ∞ b in the class of K 4 K_4 K 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 K 4 K_4 K 4 -free graphs, such that every graph G G G in this family satisfies
D 2 , ∞ b ( G ) = 425 6498 ∣ G ∣ 2 ≈ 0.0654 ⋅ ∣ G ∣ 2 . D^b_{2,\infty}(G)=\frac{425}{6498}|G|^2\approx0.0654\cdot|G|^2. D 2 , ∞ b ( G ) = 6498 425 ∣ G ∣ 2 ≈ 0.0654 ⋅ ∣ 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 G G G is a K 4 K_4 K 4 -free graph on n n n vertices, then
D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + 5 n 5 3 . D^b_{2,\infty}(G)\leq0.0671n^2+5n^{\frac{5}{3}}. D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + 5 n 3 5 .
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 n n n -blowup of a graph G G G is a graph obtained by replacing every vertex in G G G with n n n copies. Vertices in the blowup are connected if and only if their original counterparts in G G G are connected.
Lemma 2.1 ([16 ] ). If F F F is an induced subgraph of order p n + q pn+q p n + q of the n n n -blowup of C 5 C_5 C 5 , where p p p and q q q are non-negative integers with p < 5 p<5 p < 5 and q < n q<n q < n , then
e ( F ) ≥ f ( n , p , q ) : = { 0 , if p ≤ 1 , q n , if p = 2 , n 2 + 2 q n , if p = 3 , 3 n 2 + 2 q n , 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} e ( F ) ≥ f ( n , p , q ) := ⎩ ⎨ ⎧ 0 , q n , n 2 + 2 q n , 3 n 2 + 2 q n , if p ≤ 1 , if p = 2 , if p = 3 , if p = 4.
Theorem 2.2. Let G G G be a graph on 57 vertices consisting of a 5-blowup of a C 5 C_5 C 5 and an independent set on the remaining 32 vertices, with all edges between them. If G 2 n G_{2n} G 2 n is the 2 n 2n 2 n -blowup of G G G , then
D 2 , ∞ b ( G 2 n ) = 850 n 2 = 425 6498 ∣ G 2 n ∣ 2 . D^b_{2,\infty}(G_{2n})=850n^2=\frac{425}{6498}|G_{2n}|^2. D 2 , ∞ b ( G 2 n ) = 850 n 2 = 6498 425 ∣ G 2 n ∣ 2 . Proof. Let H H H be the unique copy of a 10 n 10n 10 n -blowup of C 5 C_5 C 5 in G 2 n G_{2n} G 2 n and let ( A , B ) (A,B) ( A , B ) be any balanced bipartition of V ( G 2 n ) V(G_{2n}) V ( G 2 n ) . If H H H is fully contained in A A A or B B B , then
max ( e ( A ) , e ( B ) ) = 5 ⋅ 10 n ⋅ 10 n + 7 n ⋅ 50 n = 850 n 2 . \max(e(A),e(B))=5\cdot10n\cdot10n+7n\cdot50n=850n^2. max ( e ( A ) , e ( B )) = 5 ⋅ 10 n ⋅ 10 n + 7 n ⋅ 50 n = 850 n 2 . This implies that D 2 , ∞ b ( G 2 n ) ≤ 850 n 2 D^b_{2,\infty}(G_{2n})\leq850n^2 D 2 , ∞ b ( G 2 n ) ≤ 850 n 2 . Now, consider the case in which both sides of the bipartition contain a proper subset of H H H . Without loss of generality, we can assume that A A A is the side containing the larger subset of H H H . This subset must be of size 10 p n + q 10pn+q 10 p n + q with p = 2 p=2 p = 2 and 5 n ≤ q < 10 n 5n\leq q<10n 5 n ≤ q < 10 n or with 3 ≤ p < 5 3\leq p<5 3 ≤ p < 5 and 0 ≤ q < 10 n 0\leq q<10n 0 ≤ q < 10 n .
By Theorem 2.1, the number of edges in A A A is
e ( A ) = ∣ A ∩ V ( H ) ∣ ( ∣ A ∣ − ∣ A ∩ V ( H ) ∣ ) + e ( A ∩ V ( H ) ) ≥ ( 10 p n + q ) ( 57 n − 10 p n − q ) + f ( 10 n , p , q ) = { 740 n 2 + q ( 27 n − q ) , if p = 2 , 5 n ≤ q < 10 n , 910 n 2 + q ( 17 n − q ) , if p = 3 , 0 ≤ q < 10 n , 980 n 2 − q ( 3 n + q ) , if p = 4 , 0 ≤ q < 10 n . (2) \begin{aligned}
e(A)&=|A\cap V(H)|(|A|-|A\cap V(H)|)+e(A\cap V(H))\\
&\geq(10pn+q)(57n-10pn-q)+f(10n,p,q)\\
&=
\begin{cases}
740n^2+q(27n-q), & \text{if }p=2,\ 5n\leq q<10n,\\
910n^2+q(17n-q), & \text{if }p=3,\ 0\leq q<10n,\\
980n^2-q(3n+q), & \text{if }p=4,\ 0\leq q<10n.
\end{cases} \tag*{(2)}
\end{aligned} e ( A ) = ∣ A ∩ V ( H ) ∣ ( ∣ A ∣ − ∣ A ∩ V ( H ) ∣ ) + e ( A ∩ V ( H )) ≥ ( 10 p n + q ) ( 57 n − 10 p n − q ) + f ( 10 n , p , q ) = ⎩ ⎨ ⎧ 740 n 2 + q ( 27 n − q ) , 910 n 2 + q ( 17 n − q ) , 980 n 2 − q ( 3 n + q ) , if p = 2 , 5 n ≤ q < 10 n , if p = 3 , 0 ≤ q < 10 n , if p = 4 , 0 ≤ q < 10 n . (2) Due to the basic properties of quadratic functions in a bounded range, we can conclude that e ( A ) e(A) e ( A ) is always at least 850 n 2 850n^2 850 n 2 . This gives the desired lower bound on D 2 , ∞ b ( G 2 n ) D^b_{2,\infty}(G_{2n}) D 2 , ∞ b ( G 2 n ) .
We note that assigning H H H to a single side of the partition is not the only way of attaining D 2 , ∞ b ( G 2 n ) D^{b}_{2,\infty}(G_{2n}) D 2 , ∞ b ( G 2 n ) . Denote the parts of H H H as A 1 A_1 A 1 , A 2 A_2 A 2 , A 3 A_3 A 3 , A 4 A_4 A 4 , A 5 A_5 A 5 , and consider a balanced bipartition ( A , B ) (A,B) ( A , B ) for which A 1 , A 3 ⊆ A A_1,A_3 \subseteq A A 1 , A 3 ⊆ A , A 2 , A 4 ⊆ B A_2,A_4 \subseteq B A 2 , A 4 ⊆ B , and A 5 A_5 A 5 is split evenly. Notice that for such a partition, both e ( A ) = e ( B ) e(A)=e(B) e ( A ) = e ( B ) and equality in (2) must hold. Therefore, we have
max ( e ( A ) , e ( B ) ) = 850 n 2 . \max(e(A),e(B))=850n^2. max ( e ( A ) , e ( B )) = 850 n 2 .
Our improvement on the lower bound over [16 ] stems from the fact that the equality D 2 , ∞ b ( G 2 n ) = max ( e ( A ) , e ( B ) ) D^{b}_{2,\infty}(G_{2n})=\max(e(A),e(B)) D 2 , ∞ b ( G 2 n ) = max ( e ( A ) , e ( B )) is achieved for two different partitions rather than one. Consider the class of graphs consisting of a balanced blowup of a C 5 C_5 C 5 and an independent set on the remaining vertices, with all edges between them. Notice that, for any graph in this class, the values of max ( e ( A ) , e ( B ) ) \max(e(A),e(B)) max ( e ( A ) , e ( B )) for the two extremal partitions in Theorem 2.2 can be viewed as functions of the size of the independent set. A simple analysis shows that these functions are of opposite monotonicity and the maximum of their pointwise minimum lies at the point where they are equal. This point corresponds to G 2 n G_{2n} G 2 n .
Our other experiments on this problem strongly suggest that the class described in the previous paragraph is indeed the most difficult case for this problem. Because of this, we believe that an extremal example is contained in it. As a result, we consider G 2 n G_{2n} G 2 n to be a natural candidate for an extremal example for the general problem of determining the dense half in K 4 K_4 K 4 -free graphs.
Conjecture 2.3. If G G G is a K 4 K_4 K 4 -free graph on n n n vertices, then
D 2 , ∞ b ( G ) ≤ 425 6498 n 2 + o ( n 2 ) . D^{b}_{2,\infty}(G) \le\frac{425}{6498}n^2+o(n^2). D 2 , ∞ b ( G ) ≤ 6498 425 n 2 + o ( n 2 ) .
Flag algebras
To obtain a new upper bound on D 2 , ∞ b ( G ) D^{b}_{2,\infty}(G) D 2 , ∞ b ( G ) in the class of K 4 K_4 K 4 -free graphs, we leverage the powerful framework of flag algebras developed by Razborov ([14]).
Flag algebras have proven very useful in solving various problems related to finding partitions with few edges inside each part. Some examples can be found in [10 ] , [3 ] , [15 ] and [2 ] . A typical flag algebraic application for these problems is built around picking a small substructure at random and defining the partition by splitting the vertices according to their connections to this structure. This gives inequalities which can be directly plugged into the flag algebraic framework and can lead to strong bounds, usually (but not always) with the help of a semidefinite programming solver, such as [4 ] .
It can be said that we are still in the early phases of exploring the applicability of expressing graph cuts with flag algebras, as ways to address key obstacles are still being found. For instance, [2 ] presents how this framework can be extended to analyze problems for balanced partitions, rather than arbitrary ones. The authors of [1 ] show how flag algebras on colored graphs can be used to omit unfavorable structures. In this work, we lift another limitation of this framework by showcasing how graph cuts and flag algebras can be used to argue about a non-algebraic function on the vector of numbers of edges inside the partition (though at the cost of introducing an asymptotically negligible error term).
A formal introduction to the flag-algebraic framework is beyond the scope of this paper. For this purpose, we refer the interested reader to the original paper by Razborov [14 ] .
In the remainder of this section, we introduce the notation that we use when working with flags. In this paper, we consider flags in multiple theories: 2-vertex-colored graphs, 2-vertex-colored partially oriented graphs, and 3-vertex-colored partially oriented graphs. All flags we use are K 4 K_4 K 4 -free, irrespective of coloring and orientation (that is, if we drop all colors and orientations, the graph should still be K 4 K_4 K 4 -free). In the case of partially oriented graphs, we allow orientation only between specific colors of vertices. We leverage this fact to limit the number of flags during computer-assisted calculations.
We denote untyped flags by depicting the graph using round vertices. For instance, this is the flag for the untyped triangle with two blue vertices and a single red vertex:
triangle with two blue vertices and a single red vertex \text{triangle with two blue vertices and a single red vertex} triangle with two blue vertices and a single red vertex
If we orient the edge between blue vertices, we get
triangle with two blue vertices, a single red vertex, and an oriented edge between the blue vertices \text{triangle with two blue vertices, a single red vertex, and an oriented edge between the blue vertices} triangle with two blue vertices, a single red vertex, and an oriented edge between the blue vertices
To denote a typed flag ( G , θ ) (G,\theta) ( G , θ ) of type σ \sigma σ from A σ \mathcal{A}^{\sigma} A σ , we depict G G G and signify the injective mapping θ \theta θ by writing the labels inside the vertices. The vertices in im ( θ ) \operatorname{im}(\theta) im ( θ ) are also square instead of round. For example, this is a rooted polychromatic edge with a single unlabeled red vertex connected to the blue endpoint of the edge:
rooted edge with square blue vertex labeled 1, square red vertex labeled 2, and an unlabeled red vertex connected to the blue endpoint \text{rooted edge with square blue vertex labeled 1, square red vertex labeled 2, and an unlabeled red vertex connected to the blue endpoint} rooted edge with square blue vertex labeled 1, square red vertex labeled 2, and an unlabeled red vertex connected to the blue endpoint
In our notation we also use some wildcards, which are syntactic sugar to shorten expressions where all possibilities of colors or orientations have to be considered. If a flag contains white vertices, it represents the sum of all non-isomorphic flags obtained by coloring the white vertices in all possible ways. For instance, in the theory of 2-colored graphs (where colors are red and blue), a flag with a single white vertex is shorthand for the sum of two flags
triangle with one white vertex and two blue vertices = triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices \text{triangle with one white vertex and two blue vertices}
=
\text{triangle with one red vertex and two blue vertices}
+
\text{triangle with one blue vertex and two blue vertices} triangle with one white vertex and two blue vertices = triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices
while in the theory of 3-colored flags (where colors are red, blue and cyan) it can be expanded to a sum of three summands
triangle with one white vertex and two blue vertices = triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices + triangle with one cyan vertex and two blue vertices \text{triangle with one white vertex and two blue vertices}
=
\text{triangle with one red vertex and two blue vertices}
+
\text{triangle with one blue vertex and two blue vertices}
+
\text{triangle with one cyan vertex and two blue vertices} triangle with one white vertex and two blue vertices = triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices + triangle with one cyan vertex and two blue vertices
When more white vertices are involved, the length of the sum increases and isomorphisms start playing a role. In the theory of 2-vertex-colored graphs, we have
triangle with two white vertices and one unlabeled white vertex = triangle with one red vertex and two red vertices + triangle with two red vertices and one blue vertex + triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices \text{triangle with two white vertices and one unlabeled white vertex}
=
\text{triangle with one red vertex and two red vertices}
+
\text{triangle with two red vertices and one blue vertex}
+
\text{triangle with one red vertex and two blue vertices}
+
\text{triangle with one blue vertex and two blue vertices} triangle with two white vertices and one unlabeled white vertex = triangle with one red vertex and two red vertices + triangle with two red vertices and one blue vertex + triangle with one red vertex and two blue vertices + triangle with one blue vertex and two blue vertices
When considering partially oriented graphs, we use an edge with a small dot as a template for any orientation, including the lack of it. To be precise,
undirected edge with a small dot = edge oriented in one direction + edge oriented in the other direction \text{undirected edge with a small dot}
=
\text{edge oriented in one direction}
+
\text{edge oriented in the other direction} undirected edge with a small dot = edge oriented in one direction + edge oriented in the other direction
We also combine white vertices with orientation wildcards. For instance, in the theory of 2-vertex-colored partially oriented graphs:
rooted edge with one white vertex and an orientation wildcard = rooted edge with blue unlabeled vertex and no orientation + rooted edge with blue unlabeled vertex oriented from vertex 1 to vertex 2 + rooted edge with blue unlabeled vertex oriented from vertex 2 to vertex 1 + rooted edge with red unlabeled vertex and no orientation + rooted edge with red unlabeled vertex oriented from vertex 1 to vertex 2 + rooted edge with red unlabeled vertex oriented from vertex 2 to vertex 1 \text{rooted edge with one white vertex and an orientation wildcard}
=
\text{rooted edge with blue unlabeled vertex and no orientation}
+
\text{rooted edge with blue unlabeled vertex oriented from vertex 1 to vertex 2}
+
\text{rooted edge with blue unlabeled vertex oriented from vertex 2 to vertex 1}
+
\text{rooted edge with red unlabeled vertex and no orientation}
+
\text{rooted edge with red unlabeled vertex oriented from vertex 1 to vertex 2}
+
\text{rooted edge with red unlabeled vertex oriented from vertex 2 to vertex 1} rooted edge with one white vertex and an orientation wildcard = rooted edge with blue unlabeled vertex and no orientation + rooted edge with blue unlabeled vertex oriented from vertex 1 to vertex 2 + rooted edge with blue unlabeled vertex oriented from vertex 2 to vertex 1 + rooted edge with red unlabeled vertex and no orientation + rooted edge with red unlabeled vertex oriented from vertex 1 to vertex 2 + rooted edge with red unlabeled vertex oriented from vertex 2 to vertex 1
We implicitly assume that if a flag contains objects that are not present in the currently considered theory, then its density is automatically zero and it can be safely ignored.
Linear product constraints
In a typical flag algebraic proof, one shows that constraints of the form f ≥ 0 f \ge0 f ≥ 0 hold for some f ∈ A σ f \in\mathcal{A}^{\sigma} f ∈ A σ and some type σ \sigma σ . We then apply the averaging operator and include a constraint of the form ⟦ f ⟧ ≥ 0 \llbracket f \rrbracket\ge0 [ [ f ] ] ≥ 0 in the instance of SDP that we need to solve. A popular technique to increase the ‘strength’ of the original inequality f ≥ 0 f \ge0 f ≥ 0 is to include multiple constraints of the form ⟦ f ⋅ F ⟧ ≥ 0 \llbracket f \cdot F \rrbracket\ge0 [ [ f ⋅ F ] ] ≥ 0 , where each F F F is a single partially labeled graph whose labels constitute the type σ \sigma σ .
We employ this technique for some constraints that we use in our proofs, particularly of the form ∘ − 1 − 1 2 ≥ 0 \circ\!-\!1-\frac{1}{2} \ge0 ∘ − 1 − 2 1 ≥ 0 . One can verify that a straightforward application of the averaging operator to such constraints (without the linear product extension) would yield relatively uninteresting inequalities.
Upper bound
The goal of this section is to prove Theorem 1.8. In the following theorems, we only consider graphs on an even number of vertices and prove a bound of 0.0671 n 2 + 4 n 5 3 0.0671n^2 + 4n^{\frac{5}{3}} 0.0671 n 2 + 4 n 3 5 . The proof can be extended to graphs on an odd number of vertices by removing a single vertex and adding it back to either side of the partition. This adds an extra error term of at most n n n , which is absorbed by the gap between the proven 4 n 5 3 4n^{\frac{5}{3}} 4 n 3 5 and 5 n 5 3 5n^{\frac{5}{3}} 5 n 3 5 in the exact formulation of Theorem 1.8.
For a graph G G G and two disjoint sets A , B ⊆ V ( G ) A, B \subseteq V(G) A , B ⊆ V ( G ) , by E ( A , B ) E(A, B) E ( A , B ) we denote the set of edges with one endpoint in A A A and the other in B B B , while e ( A , B ) e(A, B) e ( A , B ) is the number of such edges. Similarly, by E ( A ) E(A) E ( A ) we denote the set of edges inside A A A and by e ( A ) e(A) e ( A ) the size of this set. We use the convention that if A = ∅ A = \emptyset A = ∅ , then e ( A ) / ∣ A ∣ k = 0 e(A)/|A|^k = 0 e ( A ) /∣ A ∣ k = 0 and e ( A , B ) / ∣ A ∣ k = 0 e(A, B)/|A|^k = 0 e ( A , B ) /∣ A ∣ k = 0 for k ∈ { 1 , 2 } k \in\{1, 2\} k ∈ { 1 , 2 } . For brevity, a 2-partition V ( G ) = A ∪ B V(G) = A \cup B V ( G ) = A ∪ B is called a cut and edges within A A A or B B B are called class-edges .
We first show how graph cuts can be used to argue about asymptotic bounds on D 2 , ∞ b D^b_{2,\infty} D 2 , ∞ b . This result is a known fact (see, for example, [12 ] ), but we present its full proof to introduce proof techniques that we make heavy use of later.
Theorem 4.1. Every graph G G G on n n n vertices satisfies D 2 , ∞ b ( G ) ≤ e ( G ) 4 + n 5 3 D^b_{2,\infty}(G) \le\frac{e(G)}{4} + n^{\frac{5}{3}} D 2 , ∞ b ( G ) ≤ 4 e ( G ) + n 3 5 .
Proof. Pick a balanced bipartition ( A , B ) (A, B) ( A , B ) of V ( G ) V(G) V ( G ) uniformly at random. For an edge u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) , let X u v X_{uv} X uv be the indicator random variable of the event { u , v } ⊆ A \{u, v\} \subseteq A { u , v } ⊆ A . It is clear that
E [ X u v ] = ( n − 2 n 2 − 2 ) ( n n 2 ) = n − 2 4 ( n − 1 ) , \mathbb{E}[X_{uv}] = \frac{\binom{n-2}{\frac{n}{2}-2}}{\binom{n}{\frac{n}{2}}} = \frac{n-2}{4(n-1)}, E [ X uv ] = ( 2 n n ) ( 2 n − 2 n − 2 ) = 4 ( n − 1 ) n − 2 ,
and, since X u v X_{uv} X uv is an indicator variable,
Var [ X u v ] = E [ X u v ] − E [ X u v ] 2 = ( n − 2 ) ( 3 n − 2 ) 16 ( n − 1 ) 2 . \operatorname{Var}[X_{uv}] = \mathbb{E}[X_{uv}] - \mathbb{E}[X_{uv}]^2 = \frac{(n-2)(3n-2)}{16(n-1)^2}. Var [ X uv ] = E [ X uv ] − E [ X uv ] 2 = 16 ( n − 1 ) 2 ( n − 2 ) ( 3 n − 2 ) .
Let u v uv uv and w x wx w x be two vertex-disjoint edges in E ( G ) E(G) E ( G ) . Then
E [ X u v X w x ] = ( n − 4 n 2 − 4 ) ( n n 2 ) = ( n − 4 ) ( n − 6 ) 16 ( n − 3 ) ( n − 1 ) . \mathbb{E}[X_{uv}X_{wx}] = \frac{\binom{n-4}{\frac{n}{2}-4}}{\binom{n}{\frac{n}{2}}} = \frac{(n-4)(n-6)}{16(n-3)(n-1)}. E [ X uv X w x ] = ( 2 n n ) ( 2 n − 4 n − 4 ) = 16 ( n − 3 ) ( n − 1 ) ( n − 4 ) ( n − 6 ) .
As a result,
Cov ( X u v , X w x ) = ( n − 4 ) ( n − 6 ) 16 ( n − 3 ) ( n − 1 ) − ( n − 2 ) 2 16 ( n − 1 ) 2 = − 2 n 2 − 9 n + 6 8 ( n − 3 ) ( n − 1 ) 2 < 0. \operatorname{Cov}(X_{uv},X_{wx}) = \frac{(n-4)(n-6)}{16(n-3)(n-1)} - \frac{(n-2)^2}{16(n-1)^2} = -\frac{2n^2-9n+6}{8(n-3)(n-1)^2} < 0. Cov ( X uv , X w x ) = 16 ( n − 3 ) ( n − 1 ) ( n − 4 ) ( n − 6 ) − 16 ( n − 1 ) 2 ( n − 2 ) 2 = − 8 ( n − 3 ) ( n − 1 ) 2 2 n 2 − 9 n + 6 < 0.
Now, consider a pair of edges u v uv uv and u w uw u w , which share exactly one vertex. The formula for the expectation of the product of X u v X_{uv} X uv and X u w X_{uw} X u w changes to
E [ X u v X u w ] = ( n − 3 n 2 − 3 ) ( n n 2 ) = n − 4 8 ( n − 1 ) . \mathbb{E}[X_{uv}X_{uw}] = \frac{\binom{n-3}{\frac{n}{2}-3}}{\binom{n}{\frac{n}{2}}} = \frac{n-4}{8(n-1)}. E [ X uv X u w ] = ( 2 n n ) ( 2 n − 3 n − 3 ) = 8 ( n − 1 ) n − 4 .
This gives us the following covariance
Cov ( X u v , X u w ) = n − 4 8 ( n − 1 ) − ( n − 2 ) 2 16 ( n − 1 ) 2 = n 2 − 6 n + 4 16 ( n − 1 ) 2 . \operatorname{Cov}(X_{uv},X_{uw}) = \frac{n-4}{8(n-1)} - \frac{(n-2)^2}{16(n-1)^2} = \frac{n^2-6n+4}{16(n-1)^2}. Cov ( X uv , X u w ) = 8 ( n − 1 ) n − 4 − 16 ( n − 1 ) 2 ( n − 2 ) 2 = 16 ( n − 1 ) 2 n 2 − 6 n + 4 .
Let X X X be the random variable describing the number of class-edges inside of A A A . Clearly, X = ∑ u v ∈ E ( G ) X u v X = \sum_{uv\in E(G)} X_{uv} X = ∑ uv ∈ E ( G ) X uv , and so E [ X ] = n − 2 4 ( n − 1 ) e ( G ) \mathbb{E}[X] = \frac{n-2}{4(n-1)}e(G) E [ X ] = 4 ( n − 1 ) n − 2 e ( G ) . The variance of X X X can be upper bounded as follows,
Var ( X ) = ∑ u v ∈ E ( G ) Var ( X u v ) + ∑ u v , w x ∈ E ( G ) { u , v } ∩ { w , x } = ∅ Cov ( X u v , X w x ) + ∑ u v , u w ∈ E ( G ) v ≠ w Cov ( X u v , X u w ) ≤ ( n − 2 ) ( 3 n − 2 ) 16 ( n − 1 ) 2 ⋅ n 2 + n 2 − 6 n + 4 16 ( n − 1 ) 2 ⋅ n 3 ≤ ( n − 1 ) ( 3 n − 3 ) 16 ( n − 1 ) 2 ⋅ n 2 + n 2 − 2 n + 1 16 ( n − 1 ) 2 ⋅ n 3 ≤ n 3 4 . (3) \begin{aligned}
\operatorname{Var}(X) ={}& \sum_{uv\in E(G)} \operatorname{Var}(X_{uv}) + \sum_{\substack{uv,wx\in E(G)\\ \{u,v\}\cap\{w,x\}=\varnothing}} \operatorname{Cov}(X_{uv},X_{wx}) + \sum_{\substack{uv,uw\in E(G)\\ v\ne w}} \operatorname{Cov}(X_{uv},X_{uw}) \\
\le{}& \frac{(n-2)(3n-2)}{16(n-1)^2}\cdot n^2 + \frac{n^2-6n+4}{16(n-1)^2}\cdot n^3 \\
\le{}& \frac{(n-1)(3n-3)}{16(n-1)^2}\cdot n^2 + \frac{n^2-2n+1}{16(n-1)^2}\cdot n^3 \le\frac{n^3}{4}. \tag*{(3)}
\end{aligned} Var ( X ) = ≤ ≤ uv ∈ E ( G ) ∑ Var ( X uv ) + uv , w x ∈ E ( G ) { u , v } ∩ { w , x } = ∅ ∑ Cov ( X uv , X w x ) + uv , u w ∈ E ( G ) v = w ∑ Cov ( X uv , X u w ) 16 ( n − 1 ) 2 ( n − 2 ) ( 3 n − 2 ) ⋅ n 2 + 16 ( n − 1 ) 2 n 2 − 6 n + 4 ⋅ n 3 16 ( n − 1 ) 2 ( n − 1 ) ( 3 n − 3 ) ⋅ n 2 + 16 ( n − 1 ) 2 n 2 − 2 n + 1 ⋅ n 3 ≤ 4 n 3 . (3)
Now, a straightforward application of Chebyshev’s inequality gives
P ( X ≥ e ( G ) 4 + n 5 3 ) ≤ P ( ∣ X − n − 2 4 ( n − 1 ) e ( G ) ∣ ≥ n 5 3 ) ≤ 1 4 n 3 n 10 3 = 1 4 n 1 3 . (4) \mathbb{P}\left(X\ge\frac{e(G)}{4}+n^{\frac{5}{3}}\right)\le\mathbb{P}\left(\left|X-\frac{n-2}{4(n-1)}e(G)\right|\ge n^{\frac{5}{3}}\right)\le\frac{\frac{1}{4}n^3}{n^{\frac{10}{3}}}=\frac{1}{4n^{\frac{1}{3}}}. \tag*{(4)} P ( X ≥ 4 e ( G ) + n 3 5 ) ≤ P ( X − 4 ( n − 1 ) n − 2 e ( G ) ≥ n 3 5 ) ≤ n 3 10 4 1 n 3 = 4 n 3 1 1 . (4)
Observe that an identical inequality must hold for the random variable describing the number of class-edges inside B B B . Using a simple union bound, we can conclude that every graph must have a balanced bipartition ( A , B ) (A,B) ( A , B ) , such that max ( e ( A ) , e ( B ) ) ≤ e ( G ) 4 + n 5 3 \max(e(A),e(B))\le\frac{e(G)}{4}+n^{\frac{5}{3}} max ( e ( A ) , e ( B )) ≤ 4 e ( G ) + n 3 5 . □ \square □
Theorem 4.1 immediately proves Theorem 1.8 for small graphs.
Theorem 4.2. Every graph G G G on n ≤ 4096 n\le4096 n ≤ 4096 vertices satisfies D 2 , ∞ b ( G ) ≤ 3 n 5 3 D^b_{2,\infty}(G)\le3n^{\frac{5}{3}} D 2 , ∞ b ( G ) ≤ 3 n 3 5 .
Proof. By Theorem 4.1,
D 2 , ∞ b ( G ) ≤ e ( G ) 4 + n 5 3 ≤ n 2 8 + n 5 3 . D^b_{2,\infty}(G)\le\frac{e(G)}{4}+n^{\frac{5}{3}}\le\frac{n^2}{8}+n^{\frac{5}{3}}. D 2 , ∞ b ( G ) ≤ 4 e ( G ) + n 3 5 ≤ 8 n 2 + n 3 5 . Since for n ≤ 4096 n\le4096 n ≤ 4096 , n 2 ≤ 16 n 5 3 n^2\le16n^{\frac{5}{3}} n 2 ≤ 16 n 3 5 , this implies that D 2 , ∞ b ( G ) ≤ 3 n 5 3 D^b_{2,\infty}(G)\le3n^{\frac{5}{3}} D 2 , ∞ b ( G ) ≤ 3 n 3 5 . □ \square □
We now generalize Theorem 4.1 to more complex randomized balanced bipartitions.
Theorem 4.3. Let G G G be a graph on n > 4096 n>4096 n > 4096 vertices and let ( A , B , C ) (A,B,C) ( A , B , C ) be a (potentially unbalanced) tripartition of V ( G ) V(G) V ( G ) , such that ∣ A ∣ ≤ n 2 |A|\le\frac{n}{2} ∣ A ∣ ≤ 2 n and ∣ B ∣ ≤ n 2 |B|\le\frac{n}{2} ∣ B ∣ ≤ 2 n . Then
D 2 , ∞ b ( G ) ≤ max ( e ( A ) + n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) + ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 e ( C ) , e ( B ) + n 2 − ∣ B ∣ ∣ C ∣ ⋅ e ( B , C ) + ( n 2 − ∣ B ∣ ∣ C ∣ ) 2 e ( C ) ) + 2 n 5 3 . D^b_{2,\infty}(G)\le\max\left(e(A)+\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)+\left(\frac{\frac{n}{2}-|A|}{|C|}\right)^2e(C),\ e(B)+\frac{\frac{n}{2}-|B|}{|C|}\cdot e(B,C)+\left(\frac{\frac{n}{2}-|B|}{|C|}\right)^2e(C)\right)+2n^{\frac{5}{3}}. D 2 , ∞ b ( G ) ≤ max ( e ( A ) + ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) + ( ∣ C ∣ 2 n − ∣ A ∣ ) 2 e ( C ) , e ( B ) + ∣ C ∣ 2 n − ∣ B ∣ ⋅ e ( B , C ) + ( ∣ C ∣ 2 n − ∣ B ∣ ) 2 e ( C ) ) + 2 n 3 5 .
Proof. If ∣ C ∣ = 0 |C| = 0 ∣ C ∣ = 0 , then ( A , B ) (A,B) ( A , B ) already constitutes a balanced bipartition proving the statement.
First, we assume that C C C has at least 4 vertices and that the sizes of A A A and B B B do not exceed n 2 − 2 \frac{n}{2} - 2 2 n − 2 . The remaining case will be addressed at the end of the proof.
Let ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) be a randomized balanced bipartition obtained by randomly extending A A A and B B B to sets of size n 2 \frac{n}{2} 2 n with vertices from C C C . For any edge u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) , let X u v X_{uv} X uv be an indicator variable of the event { u , v } ⊆ A ′ \{u,v\} \subseteq A' { u , v } ⊆ A ′ . If u v ∈ E ( A , C ) uv \in E(A,C) uv ∈ E ( A , C ) , then E [ X u v ] = n 2 − ∣ A ∣ ∣ C ∣ \mathbb{E}[X_{uv}] = \frac{\frac{n}{2}-|A|}{|C|} E [ X uv ] = ∣ C ∣ 2 n − ∣ A ∣ . Whereas if u v ∈ E ( C ) uv \in E(C) uv ∈ E ( C ) , then
E [ X u v ] = ( ∣ C ∣ − 2 n 2 − ∣ A ∣ − 2 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ . \mathbb{E}[X_{uv}] = \frac{\binom{|C|-2}{\frac{n}{2}-|A|-2}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}. E [ X uv ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 2 ∣ C ∣ − 2 ) = ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) .
Now, similarly to the proof of Theorem 4.1, we want to analyze the covariance of pairs of edges that end up as class-edges in A ′ A' A ′ .
Option 1: u v , w x ∈ E ( A , C ) uv,wx \in E(A,C) uv , w x ∈ E ( A , C ) , such that u , w ∈ A u,w \in A u , w ∈ A and v ≠ x v \ne x v = x .
We have
E [ X u v X w x ] = ( ∣ C ∣ − 2 n 2 − ∣ A ∣ − 2 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ , \mathbb{E}[X_{uv}X_{wx}] = \frac{\binom{|C|-2}{\frac{n}{2}-|A|-2}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-1)\cdot|C|}, E [ X uv X w x ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 2 ∣ C ∣ − 2 ) = ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) ,
which allows us to prove the non-positivity of the covariance
Cov ( X u v , X w x ) = E [ X u v X w x ] − E [ X u v ] E [ X w x ] = ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ − ( n 2 − ∣ A ∣ ) 2 ∣ C ∣ 2 = n 2 − ∣ A ∣ ∣ C ∣ ⋅ ( n 2 − ∣ A ∣ − 1 ∣ C ∣ − 1 − n 2 − ∣ A ∣ ∣ C ∣ ) = ( n 2 − ∣ A ∣ ∣ C ∣ ) ⋅ n 2 − ∣ A ∣ − ∣ C ∣ ( ∣ C ∣ − 1 ) ∣ C ∣ ≤ 0. \begin{aligned}
\operatorname{Cov}(X_{uv},X_{wx}) &= \mathbb{E}[X_{uv}X_{wx}] - \mathbb{E}[X_{uv}]\mathbb{E}[X_{wx}] \\
&= \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-1)\cdot|C|} - \frac{\left(\frac{n}{2}-|A|\right)^2}{|C|^2} \\
&= \frac{\frac{n}{2}-|A|}{|C|}\cdot\left(\frac{\frac{n}{2}-|A|-1}{|C|-1} - \frac{\frac{n}{2}-|A|}{|C|}\right) \\
&= \left(\frac{\frac{n}{2}-|A|}{|C|}\right)\cdot\frac{\frac{n}{2}-|A|-|C|}{(|C|-1)|C|} \le0.
\end{aligned} Cov ( X uv , X w x ) = E [ X uv X w x ] − E [ X uv ] E [ X w x ] = ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) − ∣ C ∣ 2 ( 2 n − ∣ A ∣ ) 2 = ∣ C ∣ 2 n − ∣ A ∣ ⋅ ( ∣ C ∣ − 1 2 n − ∣ A ∣ − 1 − ∣ C ∣ 2 n − ∣ A ∣ ) = ( ∣ C ∣ 2 n − ∣ A ∣ ) ⋅ ( ∣ C ∣ − 1 ) ∣ C ∣ 2 n − ∣ A ∣ − ∣ C ∣ ≤ 0.
Option 2: u v , u w ∈ E ( A , C ) uv,uw \in E(A,C) uv , u w ∈ E ( A , C ) , where u ∈ C u \in C u ∈ C .
It holds that
E [ X u v X u w ] = ( ∣ C ∣ − 1 n 2 − ∣ A ∣ − 1 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = n 2 − ∣ A ∣ ∣ C ∣ , \mathbb{E}[X_{uv}X_{uw}] = \frac{\binom{|C|-1}{\frac{n}{2}-|A|-1}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\frac{n}{2}-|A|}{|C|}, E [ X uv X u w ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 1 ∣ C ∣ − 1 ) = ∣ C ∣ 2 n − ∣ A ∣ ,
so the covariance is at most
Cov ( X u v , X u w ) = n 2 − ∣ A ∣ ∣ C ∣ − ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 ≤ n 2 − ∣ A ∣ ∣ C ∣ ≤ n ∣ C ∣ . \operatorname{Cov}(X_{uv},X_{uw}) = \frac{\frac{n}{2}-|A|}{|C|} - \left(\frac{\frac{n}{2}-|A|}{|C|}\right)^2 \le\frac{\frac{n}{2}-|A|}{|C|} \le\frac{n}{|C|}. Cov ( X uv , X u w ) = ∣ C ∣ 2 n − ∣ A ∣ − ( ∣ C ∣ 2 n − ∣ A ∣ ) 2 ≤ ∣ C ∣ 2 n − ∣ A ∣ ≤ ∣ C ∣ n .
Option 3: u v ∈ E ( A , C ) uv \in E(A,C) uv ∈ E ( A , C ) , w x ∈ E ( C ) wx \in E(C) w x ∈ E ( C ) , such that v ∈ C v \in C v ∈ C , v ≠ w v \ne w v = w and v ≠ x v \ne x v = x .
In this case
E [ X u v X w x ] = ( ∣ C ∣ − 3 n 2 − ∣ A ∣ − 3 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 2 ) ⋅ ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 2 ) ⋅ ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ , \mathbb{E}[X_{uv}X_{wx}] = \frac{\binom{|C|-3}{\frac{n}{2}-|A|-3}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-2\right)\cdot\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-2)\cdot(|C|-1)\cdot|C|}, E [ X uv X w x ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 3 ∣ C ∣ − 3 ) = ( ∣ C ∣ − 2 ) ⋅ ( ∣ C ∣ − 1 ) ⋅ ∣ C ∣ ( 2 n − ∣ A ∣ − 2 ) ⋅ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) ,
which gives the following covariance
Cov ( X u v , X w x ) = E [ X u v X w x ] − E [ X u v ] E [ X w x ] = ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ − ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) 2 ( ∣ C ∣ − 1 ) ∣ C ∣ 2 = ( ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ) ( n 2 − ∣ A ∣ − 2 ∣ C ∣ − 2 − n 2 − ∣ A ∣ ∣ C ∣ ) = ( ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ) n − 2 ∣ A ∣ − 2 ∣ C ∣ ( ∣ C ∣ − 2 ) ∣ C ∣ ≤ 0. \begin{aligned}
\operatorname{Cov}(X_{uv},X_{wx}) &= \mathbb{E}[X_{uv}X_{wx}] - \mathbb{E}[X_{uv}]\mathbb{E}[X_{wx}] \\
&= \frac{\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-2)(|C|-1)|C|} - \frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)^2}{(|C|-1)|C|^2} \\
&= \left(\frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\right)\left(\frac{\frac{n}{2}-|A|-2}{|C|-2} - \frac{\frac{n}{2}-|A|}{|C|}\right) \\
&= \left(\frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\right)\frac{n-2|A|-2|C|}{(|C|-2)|C|} \le0.
\end{aligned} Cov ( X uv , X w x ) = E [ X uv X w x ] − E [ X uv ] E [ X w x ] = ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) − ( ∣ C ∣ − 1 ) ∣ C ∣ 2 ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) 2 = ( ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ) ( ∣ C ∣ − 2 2 n − ∣ A ∣ − 2 − ∣ C ∣ 2 n − ∣ A ∣ ) = ( ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ) ( ∣ C ∣ − 2 ) ∣ C ∣ n − 2∣ A ∣ − 2∣ C ∣ ≤ 0.
Option 4: u v ∈ E ( A , C ) uv \in E(A,C) uv ∈ E ( A , C ) , u w ∈ E ( C ) uw \in E(C) u w ∈ E ( C ) .
For such a pair we have
E [ X u v X u w ] = ( ∣ C ∣ − 2 n 2 − ∣ A ∣ − 2 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ \mathbb{E}[X_{uv}X_{uw}] = \frac{\binom{|C|-2}{\frac{n}{2}-|A|-2}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|} E [ X uv X u w ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 2 ∣ C ∣ − 2 ) = ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ )
which gives the following covariance
Cov ( X u v , X u w ) = E [ X u v X u w ] − E [ X u v ] E [ X u w ] = ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ − ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) 2 ( ∣ C ∣ − 1 ) ∣ C ∣ 2 = ( n 2 − ∣ A ∣ − 1 ) ⋅ ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ⋅ ∣ A ∣ + ∣ C ∣ − n 2 ∣ C ∣ ≤ n 2 ∣ C ∣ 2 . \begin{aligned}
\operatorname{Cov}(X_{uv},X_{uw}) &= \mathbb{E}[X_{uv}X_{uw}] - \mathbb{E}[X_{uv}]\mathbb{E}[X_{uw}] \\
&= \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|} - \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)^2}{(|C|-1)|C|^2} \\
&= \frac{\left(\frac{n}{2}-|A|-1\right)\cdot\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\cdot\frac{|A|+|C|-\frac{n}{2}}{|C|} \leq\frac{n^2}{|C|^2}.
\end{aligned} Cov ( X uv , X u w ) = E [ X uv X u w ] − E [ X uv ] E [ X u w ] = ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) − ( ∣ C ∣ − 1 ) ∣ C ∣ 2 ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) 2 = ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ⋅ ( 2 n − ∣ A ∣ ) ⋅ ∣ C ∣ ∣ A ∣ + ∣ C ∣ − 2 n ≤ ∣ C ∣ 2 n 2 .
Option 5: u v ∈ E ( C ) uv \in E(C) uv ∈ E ( C ) , w x ∈ E ( C ) wx \in E(C) w x ∈ E ( C ) , such that u v uv uv and w x wx w x are vertex-disjoint.
An analysis of this pair gives
E [ X u v X w x ] = ( ∣ C ∣ − 4 n 2 − ∣ A ∣ − 4 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 3 ) ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ \mathbb{E}[X_{uv}X_{wx}] = \frac{\binom{|C|-4}{\frac{n}{2}-|A|-4}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-3\right)\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-3)(|C|-2)(|C|-1)|C|} E [ X uv X w x ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 4 ∣ C ∣ − 4 ) = ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 3 ) ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ )
Fortunately, the covariance can be shown to be non-positive
Cov ( X u v , X w x ) = E [ X u v X w x ] − E [ X u v ] E [ X w x ] = ( n 2 − ∣ A ∣ − 3 ) ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ − ( n 2 − ∣ A ∣ − 1 ) 2 ( n 2 − ∣ A ∣ ) 2 ( ∣ C ∣ − 1 ) 2 ∣ C ∣ 2 = ( ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ) ⋅ ( n 2 − ∣ A ∣ − ∣ C ∣ ) ⋅ ( ( n − 2 ∣ A ∣ − 3 ) ( 2 ∣ C ∣ − 3 ) − 3 ) ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ≤ 0. \begin{aligned}
\operatorname{Cov}(X_{uv},X_{wx}) &= \mathbb{E}[X_{uv}X_{wx}] - \mathbb{E}[X_{uv}]\mathbb{E}[X_{wx}] \\
&= \frac{\left(\frac{n}{2}-|A|-3\right)\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-3)(|C|-2)(|C|-1)|C|} - \frac{\left(\frac{n}{2}-|A|-1\right)^2\left(\frac{n}{2}-|A|\right)^2}{(|C|-1)^2|C|^2} \\
&= \left(\frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\right)\cdot\frac{\left(\frac{n}{2}-|A|-|C|\right)\cdot\left((n-2|A|-3)(2|C|-3)-3\right)}{(|C|-3)(|C|-2)(|C|-1)|C|} \leq0.
\end{aligned} Cov ( X uv , X w x ) = E [ X uv X w x ] − E [ X uv ] E [ X w x ] = ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 3 ) ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) − ( ∣ C ∣ − 1 ) 2 ∣ C ∣ 2 ( 2 n − ∣ A ∣ − 1 ) 2 ( 2 n − ∣ A ∣ ) 2 = ( ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ) ⋅ ( ∣ C ∣ − 3 ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − ∣ C ∣ ) ⋅ ( ( n − 2∣ A ∣ − 3 ) ( 2∣ C ∣ − 3 ) − 3 ) ≤ 0.
Option 6: u v ∈ E ( C ) uv \in E(C) uv ∈ E ( C ) , u w ∈ E ( C ) uw \in E(C) u w ∈ E ( C ) .
In this final case we have
E [ X u v X u w ] = ( ∣ C ∣ − 3 n 2 − ∣ A ∣ − 3 ) ( ∣ C ∣ n 2 − ∣ A ∣ ) = ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ \mathbb{E}[X_{uv}X_{uw}] = \frac{\binom{|C|-3}{\frac{n}{2}-|A|-3}}{\binom{|C|}{\frac{n}{2}-|A|}} = \frac{\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-2)(|C|-1)|C|} E [ X uv X u w ] = ( 2 n − ∣ A ∣ ∣ C ∣ ) ( 2 n − ∣ A ∣ − 3 ∣ C ∣ − 3 ) = ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ )
so the covariance is at most
Cov ( X u v , X u w ) = E [ X u v X u w ] − E [ X u v ] E [ X u w ] = ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ − ( n 2 − ∣ A ∣ − 1 ) 2 ( n 2 − ∣ A ∣ ) 2 ( ∣ C ∣ − 1 ) 2 ∣ C ∣ 2 ≤ ( n 2 − ∣ A ∣ − 2 ) ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ≤ n 3 ∣ C ∣ 3 . \begin{aligned}
\operatorname{Cov}(X_{uv},X_{uw}) &= \mathbb{E}[X_{uv}X_{uw}] - \mathbb{E}[X_{uv}]\mathbb{E}[X_{uw}] \\
&= \frac{\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-2)(|C|-1)|C|} - \frac{\left(\frac{n}{2}-|A|-1\right)^2\left(\frac{n}{2}-|A|\right)^2}{(|C|-1)^2|C|^2} \\
&\leq\frac{\left(\frac{n}{2}-|A|-2\right)\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-2)(|C|-1)|C|} \leq\frac{n^3}{|C|^3}.
\end{aligned} Cov ( X uv , X u w ) = E [ X uv X u w ] − E [ X uv ] E [ X u w ] = ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) − ( ∣ C ∣ − 1 ) 2 ∣ C ∣ 2 ( 2 n − ∣ A ∣ − 1 ) 2 ( 2 n − ∣ A ∣ ) 2 ≤ ( ∣ C ∣ − 2 ) ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 2 ) ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ≤ ∣ C ∣ 3 n 3 .
We now set X X X to be the random variable describing the number of class-edges inside A ′ A' A ′ .
Its variance equals
Var ( X ) = ∑ u v ∈ E ( G ) Var ( X u v ) + ∑ u v , w x ∈ E ( G ) u v ≠ w x Cov ( X u v , X w x ) ≤ n 2 − ∣ A ∣ ∣ C ∣ ⋅ ∣ A ∣ ∣ C ∣ + ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ⋅ ∣ C ∣ 2 + n ∣ C ∣ ⋅ ∣ A ∣ 2 ∣ C ∣ + 2 ⋅ n 2 ∣ C ∣ 2 ⋅ ∣ A ∣ ∣ C ∣ 2 + n 3 ∣ C ∣ 3 ⋅ ∣ C ∣ 3 ≤ 7 n 2 12 + 9 n 3 4 ≤ 3 n 3 , (5) \begin{aligned}
\operatorname{Var}(X)=\sum_{uv\in E(G)}\operatorname{Var}(X_{uv})+\sum_{\substack{uv,wx\in E(G)\\uv\ne wx}}\operatorname{Cov}(X_{uv},X_{wx}) \\
&\le\frac{\frac{n}{2}-|A|}{|C|}\cdot|A||C|+\frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\cdot|C|^2 \\
&+\frac{n}{|C|}\cdot|A|^2|C|+2\cdot\frac{n^2}{|C|^2}\cdot|A||C|^2+\frac{n^3}{|C|^3}\cdot|C|^3 \\
&\le\frac{7n^2}{12}+\frac{9n^3}{4}\le3n^3, \tag*{(5)}
\end{aligned} Var ( X ) = uv ∈ E ( G ) ∑ Var ( X uv ) + uv , w x ∈ E ( G ) uv = w x ∑ Cov ( X uv , X w x ) ≤ ∣ C ∣ 2 n − ∣ A ∣ ⋅ ∣ A ∣∣ C ∣ + ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ⋅ ∣ C ∣ 2 + ∣ C ∣ n ⋅ ∣ A ∣ 2 ∣ C ∣ + 2 ⋅ ∣ C ∣ 2 n 2 ⋅ ∣ A ∣∣ C ∣ 2 + ∣ C ∣ 3 n 3 ⋅ ∣ C ∣ 3 ≤ 12 7 n 2 + 4 9 n 3 ≤ 3 n 3 , (5)
where the second sum runs over ordered pairs of distinct edges, so every unordered pair of edges in option 4 is counted twice. A simple calculation gives
E [ X ] = e ( A ) + n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) + ( ( n 2 − ∣ A ∣ − 1 ) ( n 2 − ∣ A ∣ ) ( ∣ C ∣ − 1 ) ∣ C ∣ ) e ( C ) ≤ e ( A ) + n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) + ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 e ( C ) , \begin{aligned}
\mathbb{E}[X]=e(A)+\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)+\left(\frac{\left(\frac{n}{2}-|A|-1\right)\left(\frac{n}{2}-|A|\right)}{(|C|-1)|C|}\right)e(C) \\
&\le e(A)+\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)+\left(\frac{\frac{n}{2}-|A|}{|C|}\right)^2e(C),
\end{aligned} E [ X ] = e ( A ) + ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) + ( ( ∣ C ∣ − 1 ) ∣ C ∣ ( 2 n − ∣ A ∣ − 1 ) ( 2 n − ∣ A ∣ ) ) e ( C ) ≤ e ( A ) + ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) + ( ∣ C ∣ 2 n − ∣ A ∣ ) 2 e ( C ) ,
and a straightforward application of Chebyshev’s inequality (analogous to the proof of Theorem 4.1 ) shows that a deviation from this expectation larger than n 5 3 n^{\frac{5}{3}} n 3 5 can only happen with probability at most 3 n − 1 3 3n^{-\frac{1}{3}} 3 n − 3 1 . An analogous bound holds for the number of class-edges inside B ′ B' B ′ . A union bound, together with the lower bound on n n n , implies that there always exists a balanced bipartition ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) in which the number of class-edges in neither part exceeds its expectation by more than n 5 3 n^{\frac{5}{3}} n 3 5 . Combined with the upper bound on the expected value, this gives
max ( e ( A ′ ) , e ( B ′ ) ) ≤ max ( e ( A ) + n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) + ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 e ( C ) , \max(e(A'),e(B'))\le\max(e(A)+\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)+(\frac{\frac{n}{2}-|A|}{|C|})^2e(C), max ( e ( A ′ ) , e ( B ′ )) ≤ max ( e ( A ) + ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) + ( ∣ C ∣ 2 n − ∣ A ∣ ) 2 e ( C ) ,
e ( B ) + n 2 − ∣ B ∣ ∣ C ∣ ⋅ e ( B , C ) + ( n 2 − ∣ B ∣ ∣ C ∣ ) 2 e ( C ) ) + n 5 3 . (6) e(B)+\frac{\frac{n}{2}-|B|}{|C|}\cdot e(B,C)+(\frac{\frac{n}{2}-|B|}{|C|})^2e(C))+n^{\frac{5}{3}}. \tag*{(6)} e ( B ) + ∣ C ∣ 2 n − ∣ B ∣ ⋅ e ( B , C ) + ( ∣ C ∣ 2 n − ∣ B ∣ ) 2 e ( C )) + n 3 5 . (6)
Inequality (6) holds under the assumptions that C C C has at least 4 vertices and the sizes of A A A and B B B do not exceed n 2 − 2 \frac{n}{2}-2 2 n − 2 . These requirements can be satisfied by moving at most 2 vertices from A A A to C C C and at most 2 vertices from B B B to C C C . Let ( A ^ , B ^ , C ^ ) (\widehat{A},\widehat{B},\widehat{C}) ( A , B , C ) be the resulting partition, for which inequality (6) holds. We have e ( A ^ ) ≤ e ( A ) e(\widehat{A})\le e(A) e ( A ) ≤ e ( A ) . Since we move at most 4 vertices to C C C , it holds that e ( A ^ , C ^ ) ≤ e ( A , C ) + 2 n e(\widehat{A},\widehat{C})\le e(A,C)+2n e ( A , C ) ≤ e ( A , C ) + 2 n and e ( C ^ ) ≤ e ( C ) + 4 n e(\widehat{C})\le e(C)+4n e ( C ) ≤ e ( C ) + 4 n . We also observe that
n 2 − ∣ A ^ ∣ ∣ C ^ ∣ − n 2 − ∣ A ∣ ∣ C ∣ ≤ n 2 − ∣ A ^ ∣ ∣ C ^ ∣ − n 2 − ∣ A ∣ ∣ C ∣ = ∣ A ∣ − ∣ A ^ ∣ ∣ C ∣ ≤ 2 ∣ C ∣ . \frac{\frac{n}{2}-|\widehat{A}|}{|\widehat{C}|}-\frac{\frac{n}{2}-|A|}{|C|}\le\frac{\frac{n}{2}-|\widehat{A}|}{|\widehat{C}|}-\frac{\frac{n}{2}-|A|}{|C|}=\frac{|A|-|\widehat{A}|}{|C|}\le\frac{2}{|C|}. ∣ C ∣ 2 n − ∣ A ∣ − ∣ C ∣ 2 n − ∣ A ∣ ≤ ∣ C ∣ 2 n − ∣ A ∣ − ∣ C ∣ 2 n − ∣ A ∣ = ∣ C ∣ ∣ A ∣ − ∣ A ∣ ≤ ∣ C ∣ 2 .
This allows us to establish
n 2 − ∣ A ^ ∣ ∣ C ^ ∣ ⋅ e ( A ^ , C ^ ) − n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) ≤ ( n 2 − ∣ A ^ ∣ ∣ C ^ ∣ − n 2 − ∣ A ∣ ∣ C ∣ ) e ( A , C ) + 2 n ≤ 2 ∣ C ∣ ⋅ e ( A , C ) + 2 n ≤ 2 ∣ A ∣ + 2 n ≤ 3 n \begin{aligned}
\frac{\frac{n}{2}-|\widehat{A}|}{|\widehat{C}|}\cdot e(\widehat{A},\widehat{C})-\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)
\le\left(\frac{\frac{n}{2}-|\widehat{A}|}{|\widehat{C}|}-\frac{\frac{n}{2}-|A|}{|C|}\right)e(A,C)+2n \\
&\le\frac{2}{|C|}\cdot e(A,C)+2n\le2|A|+2n\le3n
\end{aligned} ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) − ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) ≤ ( ∣ C ∣ 2 n − ∣ A ∣ − ∣ C ∣ 2 n − ∣ A ∣ ) e ( A , C ) + 2 n ≤ ∣ C ∣ 2 ⋅ e ( A , C ) + 2 n ≤ 2∣ A ∣ + 2 n ≤ 3 n
( ( n 2 − ∣ A ^ ∣ ∣ C ^ ∣ ) 2 − ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 ) e ( C ) + 4 n ≤ 2 ∣ C ∣ ⋅ 2 ⋅ ∣ C ∣ 2 2 + 4 n ≤ 6 n . \begin{aligned}
\left(\left(\frac{n}{2}-\frac{|\widehat{A}|}{|\widehat{C}|}\right)^2-\left(\frac{n}{2}-\frac{|A|}{|C|}\right)^2\right)e(C)+4n \\
&\le\frac{2}{|C|}\cdot2\cdot\frac{|C|^2}{2}+4n\le6n.
\end{aligned} ( 2 n − ∣ C ∣ ∣ A ∣ ) 2 − ( 2 n − ∣ C ∣ ∣ A ∣ ) 2 e ( C ) + 4 n ≤ ∣ C ∣ 2 ⋅ 2 ⋅ 2 ∣ C ∣ 2 + 4 n ≤ 6 n .
Therefore, together with inequality (6), we obtain
D 2 , ∞ b ( G ) ≤ max ( e ( A ) + n 2 − ∣ A ∣ ∣ C ∣ ⋅ e ( A , C ) + ( n 2 − ∣ A ∣ ∣ C ∣ ) 2 e ( C ) , D_{2,\infty}^{b}(G)\le\max\left(e(A)+\frac{\frac{n}{2}-|A|}{|C|}\cdot e(A,C)+\left(\frac{\frac{n}{2}-|A|}{|C|}\right)^2e(C),
\right. D 2 , ∞ b ( G ) ≤ max ( e ( A ) + ∣ C ∣ 2 n − ∣ A ∣ ⋅ e ( A , C ) + ( ∣ C ∣ 2 n − ∣ A ∣ ) 2 e ( C ) ,
e ( B ) + n 2 − ∣ B ∣ ∣ C ∣ ⋅ e ( B , C ) + ( n 2 − ∣ B ∣ ∣ C ∣ ) 2 e ( C ) ) + n 5 3 + 9 n . \left.
e(B)+\frac{\frac{n}{2}-|B|}{|C|}\cdot e(B,C)+\left(\frac{\frac{n}{2}-|B|}{|C|}\right)^2e(C)\right)+n^{\frac{5}{3}}+9n. e ( B ) + ∣ C ∣ 2 n − ∣ B ∣ ⋅ e ( B , C ) + ( ∣ C ∣ 2 n − ∣ B ∣ ) 2 e ( C ) ) + n 3 5 + 9 n .
Since for n > 27 n>27 n > 27 , we have 9 n < n 5 3 9n<n^{\frac{5}{3}} 9 n < n 3 5 , the statement follows.
Theorem 4.4. Let G G G be a graph on n > 4096 n>4096 n > 4096 vertices and let ( A , B , C , D ) (A,B,C,D) ( A , B , C , D ) be a (potentially unbalanced) partition of V ( G ) V(G) V ( G ) , such that ∣ C ∣ |C| ∣ C ∣ is even, ∣ A ∣ + ∣ C ∣ ≤ n 2 |A|+|C|\le\frac{n}{2} ∣ A ∣ + ∣ C ∣ ≤ 2 n and ∣ B ∣ + ∣ C ∣ ≤ n 2 |B|+|C|\le\frac{n}{2} ∣ B ∣ + ∣ C ∣ ≤ 2 n . Then, there exists a balanced bipartition ( C 1 , C 2 ) (C_1,C_2) ( C 1 , C 2 ) of C C C , which satisfies all of
e ( A , C 1 ) ≤ 1 2 e ( A , C ) + 1 3 n 5 3 e(A,C_1)\le\frac{1}{2}e(A,C)+\frac{1}{3}n^{\frac{5}{3}} e ( A , C 1 ) ≤ 2 1 e ( A , C ) + 3 1 n 3 5 ,
e ( B , C 2 ) ≤ 1 2 e ( B , C ) + 1 3 n 5 3 e(B,C_2)\le\frac{1}{2}e(B,C)+\frac{1}{3}n^{\frac{5}{3}} e ( B , C 2 ) ≤ 2 1 e ( B , C ) + 3 1 n 3 5 ,
e ( C 1 ) ≤ 1 4 e ( C ) + 1 3 n 5 3 e(C_1)\le\frac{1}{4}e(C)+\frac{1}{3}n^{\frac{5}{3}} e ( C 1 ) ≤ 4 1 e ( C ) + 3 1 n 3 5 ,
e ( C 2 ) ≤ 1 4 e ( C ) + 1 3 n 5 3 e(C_2)\le\frac{1}{4}e(C)+\frac{1}{3}n^{\frac{5}{3}} e ( C 2 ) ≤ 4 1 e ( C ) + 3 1 n 3 5 ,
e ( D , C 1 ) ≤ e ( C , D ) 2 + 1 3 n 5 3 e(D,C_1)\le\frac{e(C,D)}{2}+\frac{1}{3}n^{\frac{5}{3}} e ( D , C 1 ) ≤ 2 e ( C , D ) + 3 1 n 3 5 , and
e ( D , C 2 ) ≤ e ( C , D ) 2 + 1 3 n 5 3 e(D,C_2)\le\frac{e(C,D)}{2}+\frac{1}{3}n^{\frac{5}{3}} e ( D , C 2 ) ≤ 2 e ( C , D ) + 3 1 n 3 5
at once.
Proof. First, let us bound the probability that the first condition is violated by a uniformly random balanced bipartition ( C 1 , C 2 ) (C_1,C_2) ( C 1 , C 2 ) of C C C . Consider an edge u v ∈ E ( A , C ) uv\in E(A,C) uv ∈ E ( A , C ) , and let X u v X_{uv} X uv be the indicator variable of the event u v ∈ E ( A , C 1 ) uv\in E(A,C_1) uv ∈ E ( A , C 1 ) . It follows that E [ X u v ] = 1 2 \mathbb{E}[X_{uv}]=\frac{1}{2} E [ X uv ] = 2 1 and Var [ X u v ] = 1 4 \operatorname{Var}[X_{uv}]=\frac{1}{4} Var [ X uv ] = 4 1 . Now, we want to consider the covariance of the indicator variables of two edges from E ( A , C ) E(A,C) E ( A , C ) . There are two options to consider.
Option 1: u v , w x ∈ E ( A , C ) uv,wx\in E(A,C) uv , w x ∈ E ( A , C ) , with u , w ∈ A u,w\in A u , w ∈ A and v ≠ x v\ne x v = x .
We have
E [ X u v X w x ] = ( ∣ C ∣ − 2 ∣ C ∣ 2 − 2 ) ( ∣ C ∣ ∣ C ∣ 2 ) = ∣ C ∣ − 2 4 ∣ C ∣ − 4 , \mathbb{E}[X_{uv}X_{wx}]
=\frac{\binom{|C|-2}{\frac{|C|}{2}-2}}{\binom{|C|}{\frac{|C|}{2}}}
=\frac{|C|-2}{4|C|-4}, E [ X uv X w x ] = ( 2 ∣ C ∣ ∣ C ∣ ) ( 2 ∣ C ∣ − 2 ∣ C ∣ − 2 ) = 4∣ C ∣ − 4 ∣ C ∣ − 2 ,
which quickly implies Cov ( X u v , X w x ) ≤ 0 \operatorname{Cov}(X_{uv},X_{wx})\le0 Cov ( X uv , X w x ) ≤ 0 .
Option 2: u v , u w ∈ E ( A , C ) uv,uw\in E(A,C) uv , u w ∈ E ( A , C ) , such that u ∈ C u\in C u ∈ C and v ≠ w v\ne w v = w .
Since X u v X u w X_{uv}X_{uw} X uv X u w is the indicator of the event u ∈ C 1 u\in C_1 u ∈ C 1 , we have E [ X u v X u w ] = 1 2 \mathbb{E}[X_{uv}X_{uw}]=\frac{1}{2} E [ X uv X u w ] = 2 1 , which gives a covariance of exactly 1 4 \frac{1}{4} 4 1 . Similarly to the proof of Theorem 4.1 , we now consider a random variable describing the number of edges between A A A and C 1 C_1 C 1 , X = ∑ u v ∈ E ( A , C ) X u v X = \sum_{uv\in E(A,C)} X_{uv} X = ∑ uv ∈ E ( A , C ) X uv . A crude upper bound using ∣ C ∣ ≤ n 2 |C| \le\frac{n}{2} ∣ C ∣ ≤ 2 n gives
Var ( X ) = ∑ u v ∈ E ( A , C ) Var ( X u v ) + ∑ u v , u w ∈ E ( A , C ) u ∈ C , v ≠ w Cov ( X u v , X u w ) ≤ e ( A , C ) 4 + 1 4 ⋅ ∣ A ∣ 2 ⋅ ∣ C ∣ ≤ n 2 8 + n 3 8 ≤ n 3 4 . (7) \operatorname{Var}(X) = \sum_{uv\in E(A,C)} \operatorname{Var}(X_{uv}) + \sum_{\substack{uv,uw\in E(A,C) \\ u\in C,\ v\ne w}} \operatorname{Cov}(X_{uv},X_{uw})
\le\frac{e(A,C)}{4} + \frac{1}{4}\cdot|A|^2\cdot|C| \le\frac{n^2}{8}+\frac{n^3}{8}\le\frac{n^3}{4}. \tag*{(7)} Var ( X ) = uv ∈ E ( A , C ) ∑ Var ( X uv ) + uv , u w ∈ E ( A , C ) u ∈ C , v = w ∑ Cov ( X uv , X u w ) ≤ 4 e ( A , C ) + 4 1 ⋅ ∣ A ∣ 2 ⋅ ∣ C ∣ ≤ 8 n 2 + 8 n 3 ≤ 4 n 3 . (7)
Using Chebyshev’s inequality as in Theorem 4.1 , we get an upper bound on the probability of e ( A , C 1 ) e(A,C_1) e ( A , C 1 ) exceeding its expected value by at least 1 3 n 3 2 \frac{1}{3}n^{\frac{3}{2}} 3 1 n 2 3 equal to
n 3 4 ( 1 3 n 3 2 ) 2 = 9 4 n − 1 / 3 . \frac{\frac{n^3}{4}}{\left(\frac{1}{3}n^{\frac{3}{2}}\right)^2}=\frac{9}{4}n^{-1/3}. ( 3 1 n 2 3 ) 2 4 n 3 = 4 9 n − 1/3 .
The same bound holds for e ( D , C 1 ) e(D,C_1) e ( D , C 1 ) . At the same time, a bound on the probability that e ( C 1 ) e(C_1) e ( C 1 ) deviates too much can be obtained identically to Theorem 4.1 , yielding a weaker constant of 9 4 \frac{9}{4} 4 9 instead of 1 4 \frac{1}{4} 4 1 . To apply the union bound over all six conditions, we need
6 ⋅ 9 4 n − 1 / 3 < 1 , 6\cdot\frac{9}{4}n^{-1/3}<1, 6 ⋅ 4 9 n − 1/3 < 1 ,
which holds for n > 2460 n>2460 n > 2460 .
Cut definitions
We now define the cuts necessary to prove Theorem 1.8 . We heavily rely on the idea from [1 ] of endowing the graph with additional structure in order to encode extra information.
When defining inequalities that follow from the cuts, we use division, and denominators might be equal to 0 0 0 for some constructions. In the subsequent parts of the proof we use these inequalities after multiplying both sides by the common denominator. This means that they also (trivially) hold for these constructions.
Definition 4.5. Let G G G be a K 4 K_4 K 4 -free graph on n n n vertices. By L ( G ) ⊆ V ( G ) L(G)\subseteq V(G) L ( G ) ⊆ V ( G ) we denote the set of vertices with degree less than n 2 \frac{n}{2} 2 n . By H ( G ) ⊆ V ( G ) H(G)\subseteq V(G) H ( G ) ⊆ V ( G ) we denote the set of vertices with degree at least n 2 \frac{n}{2} 2 n .
We usually refer to vertices in L ( G ) L(G) L ( G ) as low-degree vertices, and to vertices in H ( G ) H(G) H ( G ) as high-degree vertices. Similarly, low-degree (respectively, high-degree) edges are edges with both endpoints in L ( G ) L(G) L ( G ) (respectively, in H ( G ) H(G) H ( G ) ).
Definition 4.6 [1 ] . For a K 4 K_4 K 4 -free graph G G G , we define its degree-colored variant as a 2-vertex-colored graph, which is obtained by coloring the vertices in L ( G ) L(G) L ( G ) blue and the vertices in H ( G ) H(G) H ( G ) red.
Later, we will extend this idea and give special meaning to edge orientation.
Definition 4.7. Let G G G be a K 4 K_4 K 4 -free graph on n n n vertices and let v ∈ V ( G ) v\in V(G) v ∈ V ( G ) be a low-degree vertex. The low-degree vertex cut is the randomized balanced bipartition ( A , A c ) (A,A^c) ( A , A c ) obtained by setting N ( v ) ⊆ A N(v)\subseteq A N ( v ) ⊆ A , and distributing the remaining vertices randomly.
Note that the upper bound on degree is necessary here to ensure formal soundness of the partition. For a fixed vertex v v v , the expected numbers of edges inside A A A and A c A^c A c are at most
e ( N ( v ) ) + n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v ) ) + ( n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) , e(N(v))+\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\cdot e(N(v),V(G)\setminus N(v))+\left(\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v)), e ( N ( v )) + n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v )) + ( n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v )) ,
and
( n 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) . \left(\frac{\frac{n}{2}}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v)). ( n − ∣ N ( v ) ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ N ( v )) .
If we now consider the limits of E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] and E [ e ( A c ) ] \mathbb{E}[e(A^c)] E [ e ( A c )] (normalized by ( n 2 ) \binom{n}{2} ( 2 n ) ) in the infinite sequence of increasing blowups of the degree-colored variant of G G G , we get the following expressions in the flag algebra of type 1 1 1 :
(flag) + ( 1 2 − (flag) ) ⋅ (flag) + ( 1 2 − (flag) ) 2 ⋅ (flag) , \text{(flag)}+\left(\frac{1}{2}-\text{(flag)}\right)\cdot\text{(flag)}+\left(\frac{1}{2}-\text{(flag)}\right)^2\cdot\text{(flag)}, (flag) + ( 2 1 − (flag) ) ⋅ (flag) + ( 2 1 − (flag) ) 2 ⋅ (flag) ,
and
( 1 2 (flag) ) 2 ⋅ (flag) . \left(\frac{\frac{1}{2}}{\text{(flag)}}\right)^2\cdot\text{(flag)}. ( (flag) 2 1 ) 2 ⋅ (flag) .
Our ultimate goal is to leverage this cut to show that no counterexample to Theorem 1.8 can exist. A typical approach, analogous to [2 ] and [1 ] , would be to use the lower bound on the numbers of edges inside this cut to show a contradiction. However, in our problem, we are considering a non-algebraic function of the vector of numbers of class-edges, which “leaks” into the inequality:
max ( (flag) + ( 1 2 − (flag) ) ⋅ (flag) + ( 1 2 − (flag) ) 2 ⋅ (flag) , ( 1 2 (flag) ) 2 ⋅ (flag) ) ≥ c , \max\left(\text{(flag)}+\left(\frac{1}{2}-\text{(flag)}\right)\cdot\text{(flag)}+\left(\frac{1}{2}-\text{(flag)}\right)^2\cdot\text{(flag)},\left(\frac{\frac{1}{2}}{\text{(flag)}}\right)^2\cdot\text{(flag)}\right)\ge c, max ( (flag) + ( 2 1 − (flag) ) ⋅ (flag) + ( 2 1 − (flag) ) 2 ⋅ (flag) , ( (flag) 2 1 ) 2 ⋅ (flag) ) ≥ c ,
where c c c is a constant, and, as a result, it cannot be used in a typical flag-algebraic computer-assisted proof. Fortunately, this cut can be transformed into a set of linear inequalities in a simple extension of the degree-colored variant of G G G .
Definition 4.8. The low-degree vertex cut colored variant of G G G is a modification of the degree-colored variant of G G G , which is obtained as a result of the following process: if a low-degree vertex v v v satisfies
e ( N ( v ) ) + n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v ) ) + ( n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) ≥ ( n 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) , (8) e(N(v))+\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\cdot e(N(v),V(G)\setminus N(v))+\left(\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v))
\ge\left(\frac{\frac{n}{2}}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v)), \tag*{(8)} e ( N ( v )) + n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v )) + ( n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v )) ≥ ( n − ∣ N ( v ) ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ N ( v )) , (8)
it remains blue, whereas if it satisfies
e ( N ( v ) ) + n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v ) ) + ( n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) < ( n 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) , (9) e(N(v))+\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\cdot e(N(v),V(G)\setminus N(v))+\left(\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v))
< \left(\frac{\frac{n}{2}}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v)), \tag*{(9)} e ( N ( v )) + n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v )) + ( n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v )) < ( n − ∣ N ( v ) ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ N ( v )) , (9)
it is recolored to cyan.
Now, because of (8), we can deduce the following identity for any blue vertex in the limit of the infinite sequence of increasing blowups of the low-degree vertex cut colored variant of G G G :
max ( blue triangle , blue edge + 1 2 − blue rooted edge blue rooted vertex blue edge + ( 1 2 − blue rooted edge blue rooted vertex ) 2 blue edge , ( 1 2 blue rooted vertex ) 2 blue edge ) = blue triangle + 1 2 − blue rooted edge blue rooted vertex blue edge + ( 1 2 − blue rooted edge blue rooted vertex ) 2 blue edge . (10) \begin{aligned}
\max\left(\text{blue triangle},\ \text{blue edge}+\frac{\frac{1}{2}-\text{blue rooted edge}}{\text{blue rooted vertex}}\text{blue edge}+\left(\frac{\frac{1}{2}-\text{blue rooted edge}}{\text{blue rooted vertex}}\right)^2\text{blue edge},\ \left(\frac{\frac{1}{2}}{\text{blue rooted vertex}}\right)^2\text{blue edge}\right) \\
&=\text{blue triangle}+\frac{\frac{1}{2}-\text{blue rooted edge}}{\text{blue rooted vertex}}\text{blue edge}+\left(\frac{\frac{1}{2}-\text{blue rooted edge}}{\text{blue rooted vertex}}\right)^2\text{blue edge}. \tag*{(10)}
\end{aligned} max ( blue triangle , blue edge + blue rooted vertex 2 1 − blue rooted edge blue edge + ( blue rooted vertex 2 1 − blue rooted edge ) 2 blue edge , ( blue rooted vertex 2 1 ) 2 blue edge ) = blue triangle + blue rooted vertex 2 1 − blue rooted edge blue edge + ( blue rooted vertex 2 1 − blue rooted edge ) 2 blue edge . (10)
Analogously, for cyan vertices we get (because of (9)):
max ( cyan triangle , cyan edge + 1 2 − cyan rooted edge cyan rooted vertex cyan edge + ( 1 2 − cyan rooted edge cyan rooted vertex ) 2 cyan edge , ( 1 2 cyan rooted vertex ) 2 cyan edge ) = ( 1 2 cyan rooted vertex ) 2 cyan edge . (11) \begin{aligned}
\max\left(\text{cyan triangle},\ \text{cyan edge}+\frac{\frac{1}{2}-\text{cyan rooted edge}}{\text{cyan rooted vertex}}\text{cyan edge}+\left(\frac{\frac{1}{2}-\text{cyan rooted edge}}{\text{cyan rooted vertex}}\right)^2\text{cyan edge},\ \left(\frac{\frac{1}{2}}{\text{cyan rooted vertex}}\right)^2\text{cyan edge}\right) \\
&=\left(\frac{\frac{1}{2}}{\text{cyan rooted vertex}}\right)^2\text{cyan edge}. \tag*{(11)}
\end{aligned} max ( cyan triangle , cyan edge + cyan rooted vertex 2 1 − cyan rooted edge cyan edge + ( cyan rooted vertex 2 1 − cyan rooted edge ) 2 cyan edge , ( cyan rooted vertex 2 1 ) 2 cyan edge ) = ( cyan rooted vertex 2 1 ) 2 cyan edge . (11)
Definition 4.9. Let G G G be a K 4 K_4 K 4 -free graph on n n n vertices and let v ∈ V ( G ) v \in V(G) v ∈ V ( G ) be a high-degree vertex. Let C C C be the smaller of the sets H ( G ) H(G) H ( G ) and L ( G ) L(G) L ( G ) . The high-degree vertex cut is the following randomized balanced bipartition ( A , A c ) (A,A^c) ( A , A c ) :
( V ( G ) ∖ N ( v ) ) ⊆ A (V(G) \setminus N(v)) \subseteq A ( V ( G ) ∖ N ( v )) ⊆ A ,
( N ( v ) ∩ C ) ⊆ A c (N(v) \cap C) \subseteq A^c ( N ( v ) ∩ C ) ⊆ A c ,
remaining vertices are distributed randomly.
For a fixed high-degree vertex v v v in a K 4 K_4 K 4 -free graph G G G , the expected numbers of class-edges inside A A A and A c A^c A c in the high-degree vertex cut based on v v v are at most
e ( V ( G ) ∖ N ( v ) ) + n 2 − ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ C ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ C ) + ( n 2 − ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ C ∣ ) 2 ⋅ e ( N ( v ) ∖ C ) , (12) e(V(G) \setminus N(v))+
\frac{\frac{n}{2}-|V(G) \setminus N(v)|}{|N(v) \setminus C|}
\cdot e(V(G) \setminus N(v),N(v) \setminus C)
+
\left(\frac{\frac{n}{2}-|V(G) \setminus N(v)|}{|N(v) \setminus C|}\right)^2
\cdot e(N(v) \setminus C), \tag*{(12)} e ( V ( G ) ∖ N ( v )) + ∣ N ( v ) ∖ C ∣ 2 n − ∣ V ( G ) ∖ N ( v ) ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ C ) + ( ∣ N ( v ) ∖ C ∣ 2 n − ∣ V ( G ) ∖ N ( v ) ∣ ) 2 ⋅ e ( N ( v ) ∖ C ) , (12)
and
e ( N ( v ) ∩ C ) + n 2 − ∣ N ( v ) ∩ C ∣ ∣ N ( v ) ∖ C ∣ e ( N ( v ) ∩ C , N ( v ) ∖ C ) + ( n 2 − ∣ N ( v ) ∩ C ∣ ∣ N ( v ) ∖ C ∣ ) 2 e ( N ( v ) ∖ C ) . (13) e(N(v) \cap C)+
\frac{\frac{n}{2}-|N(v) \cap C|}{|N(v) \setminus C|}
e(N(v) \cap C,N(v) \setminus C)
+
\left(\frac{\frac{n}{2}-|N(v) \cap C|}{|N(v) \setminus C|}\right)^2
e(N(v) \setminus C). \tag*{(13)} e ( N ( v ) ∩ C ) + ∣ N ( v ) ∖ C ∣ 2 n − ∣ N ( v ) ∩ C ∣ e ( N ( v ) ∩ C , N ( v ) ∖ C ) + ( ∣ N ( v ) ∖ C ∣ 2 n − ∣ N ( v ) ∩ C ∣ ) 2 e ( N ( v ) ∖ C ) . (13)
Unfortunately, in the language of flags, we cannot express the set C C C . Because of this, to find unique limits that are equivalent to (12) and (13), we have to consider different possibilities for which one of L ( G ) L(G) L ( G ) and H ( G ) H(G) H ( G ) is larger. If high-degree vertices are more prevalent in G G G , then the limits of E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] and E [ e ( A c ) ] \mathbb{E}[e(A^c)] E [ e ( A c )] are equivalent to the following expressions in the flag algebra of type 1 \mathbf{1} 1 :
edge + 1 2 − rooted edge rooted vertex rooted edge + ( 1 2 − rooted edge rooted vertex ) 2 rooted triangle . \text{edge}+
\frac{\frac{1}{2}-\text{rooted edge}}{\text{rooted vertex}}\text{rooted edge}+
\left(\frac{\frac{1}{2}-\text{rooted edge}}{\text{rooted vertex}}\right)^2\text{rooted triangle}. edge + rooted vertex 2 1 − rooted edge rooted edge + ( rooted vertex 2 1 − rooted edge ) 2 rooted triangle .
and
[flag-algebra expression] \text{[flag-algebra expression]} [flag-algebra expression]
If high-degree vertices constitute less than half of G G G ’s vertices, then the limits change to
[flag-algebra expression] \text{[flag-algebra expression]} [flag-algebra expression]
and
[flag-algebra expression] \text{[flag-algebra expression]} [flag-algebra expression]
Definition 4.10. Let G G G be a K 4 K_4 K 4 -free graph on n n n vertices and let u v uv uv be a high-degree edge. The high-degree edge cut is the following randomized balanced bipartition ( A , A c ) (A,A^c) ( A , A c ) :
N ( u ) ∖ N ( v ) ⊆ A N(u) \setminus N(v) \subseteq A N ( u ) ∖ N ( v ) ⊆ A ,
N ( v ) ∖ N ( u ) ⊆ A c N(v) \setminus N(u) \subseteq A^c N ( v ) ∖ N ( u ) ⊆ A c ,
V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) V(G) \setminus(N(u) \cup N(v)) V ( G ) ∖ ( N ( u ) ∪ N ( v )) is randomly split into two balanced parts, one of which is included in A A A ,
remaining vertices are distributed randomly.
Notice that the high-degree requirement is essential for the soundness of this definition – since deg ( u ) ≥ n 2 \deg(u) \ge\frac{n}{2} deg ( u ) ≥ 2 n , we know that ∣ N ( v ) ∖ N ( u ) ∣ + 1 2 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ∣ ≤ n 2 |N(v) \setminus N(u)| + \frac{1}{2}|V(G) \setminus(N(u) \cup N(v))| \le\frac{n}{2} ∣ N ( v ) ∖ N ( u ) ∣ + 2 1 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v )) ∣ ≤ 2 n , and symmetrically for v v v . Denote by N ( u , v ) = N ( u ) ∩ N ( v ) N(u,v) = N(u) \cap N(v) N ( u , v ) = N ( u ) ∩ N ( v ) the common neighborhood of u u u and v v v . For a fixed high-degree edge u v uv uv , E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] is at most
e ( N ( u ) ∖ N ( v ) ) + 1 2 e ( N ( u ) ∖ N ( v ) , V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) + 1 4 e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) + n 2 − ∣ N ( u ) ∖ N ( v ) ∣ − 1 2 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ∣ ∣ N ( u , v ) ∣ ⋅ e ( N ( u ) ∖ N ( v ) , N ( u , v ) ) + n 4 − 1 2 ∣ N ( u ) ∖ N ( v ) ∣ − 1 4 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ∣ ∣ N ( u , v ) ∣ ⋅ e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) , N ( u , v ) ) , \begin{aligned}
e(N(u) \setminus N(v))+\frac{1}{2}e(N(u) \setminus N(v),V(G) \setminus(N(u)\cup N(v)))+\frac{1}{4}e(V(G)\setminus(N(u)\cup N(v))) \\
&+\frac{\frac n2-|N(u)\setminus N(v)|-\frac12|V(G)\setminus(N(u)\cup N(v))|}{|N(u,v)|}\cdot e(N(u)\setminus N(v),N(u,v)) \\
&+\frac{\frac n4-\frac12|N(u)\setminus N(v)|-\frac14|V(G)\setminus(N(u)\cup N(v))|}{|N(u,v)|}\cdot e(V(G)\setminus(N(u)\cup N(v)),N(u,v)),
\end{aligned} e ( N ( u ) ∖ N ( v )) + 2 1 e ( N ( u ) ∖ N ( v ) , V ( G ) ∖ ( N ( u ) ∪ N ( v ))) + 4 1 e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ))) + ∣ N ( u , v ) ∣ 2 n − ∣ N ( u ) ∖ N ( v ) ∣ − 2 1 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v )) ∣ ⋅ e ( N ( u ) ∖ N ( v ) , N ( u , v )) + ∣ N ( u , v ) ∣ 4 n − 2 1 ∣ N ( u ) ∖ N ( v ) ∣ − 4 1 ∣ V ( G ) ∖ ( N ( u ) ∪ N ( v )) ∣ ⋅ e ( V ( G ) ∖ ( N ( u ) ∪ N ( v )) , N ( u , v )) ,
while E [ e ( A c ) ] \mathbb{E}[e(A^c)] E [ e ( A c )] is at most
e ( N ( v ) ∖ N ( u ) ) + 1 2 e ( N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) + 1 4 e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) + n 2 − ∣ N ( v ) ∖ N ( u ) ∣ − 1 2 ∣ V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ∣ ∣ N ( v , u ) ∣ ⋅ e ( N ( v ) ∖ N ( u ) , N ( v , u ) ) + n 4 − 1 2 ∣ N ( v ) ∖ N ( u ) ∣ − 1 4 ∣ V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ∣ ∣ N ( v , u ) ∣ ⋅ e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) , N ( v , u ) ) . \begin{aligned}
e(N(v) \setminus N(u))+\frac{1}{2}e(N(v) \setminus N(u),V(G) \setminus(N(v)\cup N(u)))+\frac{1}{4}e(V(G)\setminus(N(v)\cup N(u))) \\
&+\frac{\frac n2-|N(v)\setminus N(u)|-\frac12|V(G)\setminus(N(v)\cup N(u))|}{|N(v,u)|}\cdot e(N(v)\setminus N(u),N(v,u)) \\
&+\frac{\frac n4-\frac12|N(v)\setminus N(u)|-\frac14|V(G)\setminus(N(v)\cup N(u))|}{|N(v,u)|}\cdot e(V(G)\setminus(N(v)\cup N(u)),N(v,u)).
\end{aligned} e ( N ( v ) ∖ N ( u )) + 2 1 e ( N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( v ) ∪ N ( u ))) + 4 1 e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ))) + ∣ N ( v , u ) ∣ 2 n − ∣ N ( v ) ∖ N ( u ) ∣ − 2 1 ∣ V ( G ) ∖ ( N ( v ) ∪ N ( u )) ∣ ⋅ e ( N ( v ) ∖ N ( u ) , N ( v , u )) + ∣ N ( v , u ) ∣ 4 n − 2 1 ∣ N ( v ) ∖ N ( u ) ∣ − 4 1 ∣ V ( G ) ∖ ( N ( v ) ∪ N ( u )) ∣ ⋅ e ( V ( G ) ∖ ( N ( v ) ∪ N ( u )) , N ( v , u )) .
The limits of these expressions in the infinite sequence of increasing blowups of the degree-colored variant of G G G are in the flag algebra of type 1 2 1\,2 1 2 :
[flag-algebra expression] (14) \text{[flag-algebra expression]} \tag*{(14)} [flag-algebra expression] (14)
[graph expression] + 1 2 [graph expression] + 1 4 [graph expression] + 1 2 − [graph expression] [graph expression] + 1 4 − 1 2 [graph expression] [graph expression] + [graph expression] . \text{[graph expression]} + \frac{1}{2}\text{[graph expression]} + \frac{1}{4}\text{[graph expression]} + \frac{\frac{1}{2}-\text{[graph expression]}}{\text{[graph expression]}} + \frac{\frac{1}{4}-\frac{1}{2}\text{[graph expression]}}{\text{[graph expression]}} + \text{[graph expression]}. [graph expression] + 2 1 [graph expression] + 4 1 [graph expression] + [graph expression] 2 1 − [graph expression] + [graph expression] 4 1 − 2 1 [graph expression] + [graph expression] .
This cut, analogously to the low-degree vertex cut, is difficult to apply directly in the form of linear flag constraints. Similarly, we address this by considering an extension of our original graph, where information is directly encoded in its components.
Definition 4.11. The high-degree edge cut oriented variant of G G G is a partially oriented, vertex-colored graph, which is obtained as a result of the following modification of the low-degree vertex cut colored variant of G G G :
For every high-degree edge u v uv uv , consider the high-degree edge cut ( A , A c ) (A,A^{c}) ( A , A c ) based on this edge. If the above upper bound on E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] is at least the above upper bound on E [ e ( A c ) ] \mathbb{E}[e(A^{c})] E [ e ( A c )] , orient this edge from v v v to u u u . Otherwise, orient it from u u u to $v.
For any choice of labels, the following relation must hold in the limit of the infinite sequence of increasing blowups of a high-degree edge cut oriented variant of a K 4 K_{4} K 4 -free graph G G G :
[graph expression] ≥ [graph expression] . (15) \text{[graph expression]}
\geq
\text{[graph expression]}. \tag*{(15)} [graph expression] ≥ [graph expression] . (15)
Definition 4.12. Let G G G be a K 4 K_{4} K 4 -free graph on n n n vertices and let u v uv uv be a low-degree edge. The low-degree edge cut is the randomized balanced bipartition ( A , A c ) (A,A^{c}) ( A , A c ) obtained by setting N ( u ) ∖ N ( v ) ⊆ A N(u)\setminus N(v)\subseteq A N ( u ) ∖ N ( v ) ⊆ A , N ( v ) ∖ N ( u ) ⊆ A c N(v)\setminus N(u)\subseteq A^{c} N ( v ) ∖ N ( u ) ⊆ A c and distributing the remaining vertices randomly.
The deterministically assigned sets N ( u ) ∖ N ( v ) N(u)\setminus N(v) N ( u ) ∖ N ( v ) and N ( v ) ∖ N ( u ) N(v)\setminus N(u) N ( v ) ∖ N ( u ) have fewer than n 2 \frac{n}{2} 2 n vertices, since u u u and v v v are low-degree vertices. For a fixed low-degree edge u v uv uv , E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] is at most
e ( N ( u ) ∖ N ( v ) ) + n 2 − ∣ N ( u ) ∖ N ( v ) ∣ ∣ ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) ∪ N ( u , v ) ∣ ⋅ ( e ( N ( u ) ∖ N ( v ) , V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) + e ( N ( u ) ∖ N ( v ) , N ( u , v ) ) ) + ( n 2 − ∣ N ( u ) ∖ N ( v ) ∣ ∣ ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) ∪ N ( u , v ) ∣ ) 2 ⋅ ( e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) ) + e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) , N ( u , v ) ) ) , \begin{aligned}
&e(N(u)\setminus N(v))+
\frac{\frac{n}{2}-|N(u)\setminus N(v)|}
{|(V(G)\setminus(N(u)\cup N(v)))\cup N(u,v)|}\\
&\quad\cdot\bigl(e(N(u)\setminus N(v),V(G)\setminus(N(u)\cup N(v)))+e(N(u)\setminus N(v),N(u,v))\bigr)\\
&\quad+
\left(\frac{\frac{n}{2}-|N(u)\setminus N(v)|}
{|(V(G)\setminus(N(u)\cup N(v)))\cup N(u,v)|}\right)^{2}\\
&\quad\cdot\bigl(e(V(G)\setminus(N(u)\cup N(v)))+e(V(G)\setminus(N(u)\cup N(v)),N(u,v))\bigr),
\end{aligned} e ( N ( u ) ∖ N ( v )) + ∣ ( V ( G ) ∖ ( N ( u ) ∪ N ( v ))) ∪ N ( u , v ) ∣ 2 n − ∣ N ( u ) ∖ N ( v ) ∣ ⋅ ( e ( N ( u ) ∖ N ( v ) , V ( G ) ∖ ( N ( u ) ∪ N ( v ))) + e ( N ( u ) ∖ N ( v ) , N ( u , v )) ) + ( ∣ ( V ( G ) ∖ ( N ( u ) ∪ N ( v ))) ∪ N ( u , v ) ∣ 2 n − ∣ N ( u ) ∖ N ( v ) ∣ ) 2 ⋅ ( e ( V ( G ) ∖ ( N ( u ) ∪ N ( v ))) + e ( V ( G ) ∖ ( N ( u ) ∪ N ( v )) , N ( u , v )) ) ,
while E [ e ( A c ) ] \mathbb{E}[e(A^{c})] E [ e ( A c )] is at most
e ( N ( v ) ∖ N ( u ) ) + n 2 − ∣ N ( v ) ∖ N ( u ) ∣ ∣ ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) ∪ N ( u , v ) ∣ ⋅ ( e ( N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) + e ( N ( v ) ∖ N ( u ) , N ( v , u ) ) ) + ( n 2 − ∣ N ( v ) ∖ N ( u ) ∣ ∣ ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) ∪ N ( u , v ) ∣ ) 2 ⋅ ( e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) ) + e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ) ) , N ( v , u ) ) ) . \begin{aligned}
&e(N(v)\setminus N(u))+
\frac{\frac{n}{2}-|N(v)\setminus N(u)|}
{|(V(G)\setminus(N(v)\cup N(u)))\cup N(u,v)|}\\
&\quad\cdot\bigl(e(N(v)\setminus N(u),V(G)\setminus(N(v)\cup N(u)))+e(N(v)\setminus N(u),N(v,u))\bigr)\\
&\quad+
\left(\frac{\frac{n}{2}-|N(v)\setminus N(u)|}
{|(V(G)\setminus(N(v)\cup N(u)))\cup N(u,v)|}\right)^{2}\\
&\quad\cdot\bigl(e(V(G)\setminus(N(v)\cup N(u)))+e(V(G)\setminus(N(v)\cup N(u)),N(v,u))\bigr).
\end{aligned} e ( N ( v ) ∖ N ( u )) + ∣ ( V ( G ) ∖ ( N ( v ) ∪ N ( u ))) ∪ N ( u , v ) ∣ 2 n − ∣ N ( v ) ∖ N ( u ) ∣ ⋅ ( e ( N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( v ) ∪ N ( u ))) + e ( N ( v ) ∖ N ( u ) , N ( v , u )) ) + ( ∣ ( V ( G ) ∖ ( N ( v ) ∪ N ( u ))) ∪ N ( u , v ) ∣ 2 n − ∣ N ( v ) ∖ N ( u ) ∣ ) 2 ⋅ ( e ( V ( G ) ∖ ( N ( v ) ∪ N ( u ))) + e ( V ( G ) ∖ ( N ( v ) ∪ N ( u )) , N ( v , u )) ) .
This time, the limits are in the algebra of type 1 2 1\ 2 1 2 :
[graph expression] + 1 2 − [graph expression] [graph expression] + [graph expression] [graph expression] + ( 1 2 − [graph expression] [graph expression] + [graph expression] ) 2 [graph expression] . \text{[graph expression]} + \frac{\frac{1}{2}-\text{[graph expression]}}{\text{[graph expression]}+\text{[graph expression]}}\text{[graph expression]}+\left(\frac{\frac{1}{2}-\text{[graph expression]}}{\text{[graph expression]}+\text{[graph expression]}}\right)^2\text{[graph expression]}. [graph expression] + [graph expression] + [graph expression] 2 1 − [graph expression] [graph expression] + ( [graph expression] + [graph expression] 2 1 − [graph expression] ) 2 [graph expression] .
and
[graph expression] + 1 2 − [graph expression] [graph expression] + [graph expression] [graph expression] + ( 1 2 − [graph expression] [graph expression] + [graph expression] ) 2 [graph expression] . \text{[graph expression]} + \frac{\frac{1}{2}-\text{[graph expression]}}{\text{[graph expression]}+\text{[graph expression]}}\text{[graph expression]}+\left(\frac{\frac{1}{2}-\text{[graph expression]}}{\text{[graph expression]}+\text{[graph expression]}}\right)^2\text{[graph expression]}. [graph expression] + [graph expression] + [graph expression] 2 1 − [graph expression] [graph expression] + ( [graph expression] + [graph expression] 2 1 − [graph expression] ) 2 [graph expression] .
Similarly to the high-degree edge cut, we need to define an extension of G G G , in which the limits of the expected numbers of class-edges will be usable in the form of linear constraints.
Definition 4.13. The low-degree edge cut oriented variant of G G G is a partially oriented, vertex-colored graph, which is obtained as a result of the following modification of the degree-colored variant of G G G :
For every low-degree edge u v uv uv , consider the low-degree edge cut ( A , A c ) (A,A^c) ( A , A c ) based on this edge. If the above upper bound on E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] is at least the above upper bound on E [ e ( A c ) ] \mathbb{E}[e(A^c)] E [ e ( A c )] , orient this edge from v v v to u u u . Otherwise, orient it from u u u to $v.
In the limit of the infinite sequence of increasing blowups of a low-degree edge cut oriented variant of some K 4 K_4 K 4 -free graph G G G , a relationship analogous to (15) must hold:
[graph expression] ≥ [graph expression] . (16) \text{[graph expression]} \geq\text{[graph expression]}. \tag*{(16)} [graph expression] ≥ [graph expression] . (16)
Definition 4.14. Let G G G be a K 4 K_4 K 4 -free graph on n n n vertices. Let C C C be the smaller of the sets H ( G ) H(G) H ( G ) and L ( G ) L(G) L ( G ) . The degree cut is the randomized balanced bipartition ( A , A c ) (A,A^c) ( A , A c ) obtained by setting C ⊆ A C \subseteq A C ⊆ A and distributing the remaining vertices randomly.
The expected numbers of class-edges inside A A A and A c A^c A c are at most
e ( C ) + n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) , e(C)+\frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\cdot e(C,V(G)\setminus C)+\left(\frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C), e ( C ) + ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) ,
and
( n 2 ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) . \left(\frac{\frac{n}{2}}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C). ( ∣ V ( G ) ∖ C ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ C ) .
If low-degree vertices are more prevalent in G G G , then the limits of E [ e ( A ) ] \mathbb{E}[e(A)] E [ e ( A )] and E [ e ( A c ) ] \mathbb{E}[e(A^c)] E [ e ( A c )] are the following expressions in the flag algebra of unrooted type:
[red graph expression] , [blue graph expression] . \text{[red graph expression]}, \qquad\text{[blue graph expression]}. [red graph expression] , [blue graph expression] .
In the case where high-degree vertices are more common, we get the following expressions:
[blue graph expression] , [red graph expression] . \text{[blue graph expression]}, \qquad\text{[red graph expression]}. [blue graph expression] , [red graph expression] .
Notice that, contrary to the previous cuts, the expected number of class-edges for this cut is a global property of the graph, rather than a local one. As a result, we can work around the presence of the max function by separating graphs into classes based on where the maximum is achieved. For instance, if we limit ourselves to the class of graphs in which the following inequality holds:
e ( C ) + n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) ≥ ( n 2 ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) , \begin{aligned}
e(C) &+ \frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\cdot e(C,V(G)\setminus C) + \left(\frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C) \\
&\ge\left(\frac{\frac{n}{2}}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C),
\end{aligned} e ( C ) + ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) ≥ ( ∣ V ( G ) ∖ C ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ C ) ,
we can freely use the degree cut, as in this class the following trivially holds:
max ( e ( C ) + n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) , ( n 2 ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) ) = e ( C ) + n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( n 2 − ∣ C ∣ ∣ V ( G ) ∖ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) . \begin{aligned}
\max\Biggl(&e(C) + \frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\cdot e(C,V(G)\setminus C) + \left(\frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C),\\
&\left(\frac{\frac{n}{2}}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C)\Biggr) \\
&= e(C) + \frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\cdot e(C,V(G)\setminus C) + \left(\frac{\frac{n}{2}-|C|}{|V(G)\setminus C|}\right)^2\cdot e(V(G)\setminus C).
\end{aligned} max ( e ( C ) + ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) , ( ∣ V ( G ) ∖ C ∣ 2 n ) 2 ⋅ e ( V ( G ) ∖ C ) ) = e ( C ) + ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ⋅ e ( C , V ( G ) ∖ C ) + ( ∣ V ( G ) ∖ C ∣ 2 n − ∣ C ∣ ) 2 ⋅ e ( V ( G ) ∖ C ) .
When considering the limits of graph sequences, a formally sound usage of the degree cut requires an analysis of four different cases as we have to account for the fact that there are two possibilities for what the set C C C actually represents.
Proof of the upper bound
We now combine all the cuts and related graph extensions defined above to prove a new upper bound on D 2 , ∞ b D^{b}_{2,\infty} D 2 , ∞ b in the class of K 4 K_4 K 4 -free graphs.
Proof of Theorem 1.8 . If G G G has at most 4096 vertices, we are done by Theorem 4.2 , so we may assume that n > 4096 n > 4096 n > 4096 . As explained at the beginning of this section, we will prove the bound D 2 , ∞ b ( G ) < 0.0671 n 2 + 4 n 5 / 3 D^{b}_{2,\infty}(G) < 0.0671n^2 + 4n^{5/3} D 2 , ∞ b ( G ) < 0.0671 n 2 + 4 n 5/3 for even n n n , which implies the desired general bound D 2 , ∞ b ( G ) < 0.0671 n 2 + 5 n 5 / 3 D^{b}_{2,\infty}(G) < 0.0671n^2 + 5n^{5/3} D 2 , ∞ b ( G ) < 0.0671 n 2 + 5 n 5/3 for arbitrary n n n .
As mentioned in the proof of Theorem 2.2 , we know two cuts which are tight for the conjectured extremal example. In the nomenclature used in this section, these are the high-degree edge cut and the degree cut. The remaining cuts are used to eliminate degenerate constructions which are so far from the extremal example that the optimal cuts are no longer relevant.
We have observed that a formally sound application of the degree cut requires an analysis of four separate graph classes. In addition, we need to handle graphs with a small density of high-degree edges separately, as for them the high-degree edge cut gives no useful information. This, in total, gives 8 different cases.
In each of these cases, we show that for at least one of the cuts defined in § 4.1 the maximum of expected values of the number of class-edges inside the two sides of the cut is below our upper bound. To do this, we consider the limit of the infinite sequence of increasing blowups of the low-degree (or high-degree) edge cut oriented variant of the graph, and leverage an SDP solver to show that a graphon for which every cut would “exceed” our upper bound cannot exist.
We first outline a set of base inequalities that will be relevant in the computer-assisted flag algebraic part of every case. Our usage of colored vertices clearly implies
blue vertex ≤ 1 2 , (17) \text{blue vertex} \le\frac{1}{2}, \tag*{(17)} blue vertex ≤ 2 1 , (17)
cyan vertex ≤ 1 2 , (18) \text{cyan vertex} \le\frac{1}{2}, \tag*{(18)} cyan vertex ≤ 2 1 , (18)
red vertex ≥ 1 2 . (19) \text{red vertex} \ge\frac{1}{2}. \tag*{(19)} red vertex ≥ 2 1 . (19)
and, as a consequence of the fully random partition,
1 4 (colored edge) ≥ 0.0671 ⋅ 2. (20) \frac{1}{4}\text{(colored edge)} \ge0.0671\cdot2. \tag*{(20)} 4 1 (colored edge) ≥ 0.0671 ⋅ 2. (20)
Case 1: In this case, we consider a K 4 K_4 K 4 -free graph G G G which satisfies the following set of inequalities:
∣ L ( G ) ∣ n ≥ 1 2 , (21) \frac{|L(G)|}{n} \ge\frac{1}{2}, \tag*{(21)} n ∣ L ( G ) ∣ ≥ 2 1 , (21)
e ( H ( G ) ) ( n 2 ) ≥ 0.02 , (22) \frac{e(H(G))}{\binom{n}{2}} \ge0.02, \tag*{(22)} ( 2 n ) e ( H ( G )) ≥ 0.02 , (22)
and
e ( H ( G ) ) + n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ e ( L ( G ) , H ( G ) ) + ( n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ) 2 e ( L ( G ) ) ≥ ( n 2 ∣ L ( G ) ∣ ) 2 e ( L ( G ) ) . (23) e(H(G))+\frac{\frac{n}{2}-|H(G)|}{|L(G)|}e(L(G),H(G))+\left(\frac{\frac{n}{2}-|H(G)|}{|L(G)|}\right)^2e(L(G))
\ge\left(\frac{\frac{n}{2}}{|L(G)|}\right)^2e(L(G)). \tag*{(23)} e ( H ( G )) + ∣ L ( G ) ∣ 2 n − ∣ H ( G ) ∣ e ( L ( G ) , H ( G )) + ( ∣ L ( G ) ∣ 2 n − ∣ H ( G ) ∣ ) 2 e ( L ( G )) ≥ ( ∣ L ( G ) ∣ 2 n ) 2 e ( L ( G )) . (23)
For contradiction, assume that D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 5 3 D^{b}_{2,\infty}(G)>0.0671n^2+4n^{\frac{5}{3}} D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 3 5 . Let R R R be the high-degree edge cut oriented variant of G G G . We now consider the graphon W W W , which is the limit of the infinite sequence of increasing blowups of R R R . It is clear that, as a consequence of (20), (21), and (22), W W W has to satisfy
blue vertex + cyan vertex ≥ 1 2 , (24) \text{blue vertex}+\text{cyan vertex}\ge\frac{1}{2}, \tag*{(24)} blue vertex + cyan vertex ≥ 2 1 , (24)
red edge ≥ 0.02 , (25) \text{red edge}\ge0.02, \tag*{(25)} red edge ≥ 0.02 , (25)
and
red edge + 1 2 − red vertex blue vertex + cyan vertex mixed edges + ( 1 2 − red vertex blue vertex + cyan vertex ) 2 same-color edges ≥ ( 1 2 blue vertex + cyan vertex ) 2 same-color edges . (26) \text{red edge}+\frac{\frac{1}{2}-\text{red vertex}}{\text{blue vertex}+\text{cyan vertex}}\text{mixed edges}
+\left(\frac{\frac{1}{2}-\text{red vertex}}{\text{blue vertex}+\text{cyan vertex}}\right)^2
\text{same-color edges}
\ge
\left(\frac{\frac{1}{2}}{\text{blue vertex}+\text{cyan vertex}}\right)^2
\text{same-color edges}. \tag*{(26)} red edge + blue vertex + cyan vertex 2 1 − red vertex mixed edges + ( blue vertex + cyan vertex 2 1 − red vertex ) 2 same-color edges ≥ ( blue vertex + cyan vertex 2 1 ) 2 same-color edges . (26)
For every blue vertex in R R R it must hold that
e ( N ( v ) ) + n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v ) ) + ( n 2 − ∣ N ( v ) ∣ n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v ) ) ≥ 0.0671 n 2 . e(N(v))+\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\cdot e(N(v),V(G)\setminus N(v))
+\left(\frac{\frac{n}{2}-|N(v)|}{n-|N(v)|}\right)^2\cdot e(V(G)\setminus N(v))
\ge0.0671n^2. e ( N ( v )) + n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ⋅ e ( N ( v ) , V ( G ) ∖ N ( v )) + ( n − ∣ N ( v ) ∣ 2 n − ∣ N ( v ) ∣ ) 2 ⋅ e ( V ( G ) ∖ N ( v )) ≥ 0.0671 n 2 .
After applying the standard normalization by ( n 2 ) \binom{n}{2} ( 2 n ) and considering the limit, we get that the following must hold for W W W :
triangle with one labeled blue vertex + 1 2 − edge with one labeled blue vertex + edge with one labeled blue vertex + ( 1 2 − edge with one labeled blue vertex ) 2 + edge ≥ 0.0671 ⋅ 2 (27) \text{triangle with one labeled blue vertex}+\frac{1}{2}-\text{edge with one labeled blue vertex}+\text{edge with one labeled blue vertex}+\left(\frac{1}{2}-\text{edge with one labeled blue vertex}\right)^2+\text{edge}\ge0.0671\cdot2 \tag*{(27)} triangle with one labeled blue vertex + 2 1 − edge with one labeled blue vertex + edge with one labeled blue vertex + ( 2 1 − edge with one labeled blue vertex ) 2 + edge ≥ 0.0671 ⋅ 2 (27)
which can be rewritten as
( triangle − 0.1342 ) ⋅ edge 2 + ( 1 2 − edge ) ⋅ edge ⋅ edge + ( 1 2 − edge ) 2 edge ≥ 0. (28) \left(\text{triangle}-0.1342\right)\cdot\text{edge}^{2}+\left(\frac{1}{2}-\text{edge}\right)\cdot\text{edge}\cdot\text{edge}+\left(\frac{1}{2}-\text{edge}\right)^2\text{edge}\ge0. \tag*{(28)} ( triangle − 0.1342 ) ⋅ edge 2 + ( 2 1 − edge ) ⋅ edge ⋅ edge + ( 2 1 − edge ) 2 edge ≥ 0. (28)
We can then apply the averaging operator and get a linear constraint of the form
[ ( triangle − 0.1342 ) ⋅ edge 2 + ( 1 2 − edge ) ⋅ edge ⋅ edge + ( 1 2 − edge ) 2 edge ] ≥ 0. (29) \left[\left(\text{triangle}-0.1342\right)\cdot\text{edge}^{2}+\left(\frac{1}{2}-\text{edge}\right)\cdot\text{edge}\cdot\text{edge}+\left(\frac{1}{2}-\text{edge}\right)^2\text{edge}\right]\ge0. \tag*{(29)} [ ( triangle − 0.1342 ) ⋅ edge 2 + ( 2 1 − edge ) ⋅ edge ⋅ edge + ( 2 1 − edge ) 2 edge ] ≥ 0. (29)
As a consequence of (10) , W W W must satisfy for any choice of the labeled blue vertex
edge + 1 2 − edge + edge + ( 1 2 − edge ) 2 edge ≥ ( 1 2 ) 2 edge , (30) \text{edge}+\frac{1}{2}-\text{edge}+\text{edge}+\left(\frac{1}{2}-\text{edge}\right)^2\text{edge}\ge\left(\frac{1}{2}\right)^2\text{edge}, \tag*{(30)} edge + 2 1 − edge + edge + ( 2 1 − edge ) 2 edge ≥ ( 2 1 ) 2 edge , (30)
which can be multiplied and averaged to
[ triangle ⋅ edge 2 + ( 1 2 − edge ) ⋅ edge ⋅ edge − ( edge − edge ) 2 edge ] ≥ 0. (31) \left[\text{triangle}\cdot\text{edge}^{2}+\left(\frac{1}{2}-\text{edge}\right)\cdot\text{edge}\cdot\text{edge}-\left(\text{edge}-\text{edge}\right)^2\text{edge}\right]\ge0. \tag*{(31)} [ triangle ⋅ edge 2 + ( 2 1 − edge ) ⋅ edge ⋅ edge − ( edge − edge ) 2 edge ] ≥ 0. (31)
For cyan vertices, we get analogous constraints in the form of
[ 1 4 edge − 0.1342 ⋅ edge 2 ] ≥ 0 , (32) \left[\frac{1}{4}\text{edge}-0.1342\cdot\text{edge}^{2}\right]\ge0, \tag*{(32)} [ 4 1 edge − 0.1342 ⋅ edge 2 ] ≥ 0 , (32)
and
[ ( edge − edge ) 2 edge − edge ⋅ triangle ⋅ edge 2 − ( 1 2 − edge ) ⋅ edge ⋅ edge ] ≥ 0. (33) \left[\left(\text{edge}-\text{edge}\right)^2\text{edge}-\text{edge}\cdot\text{triangle}\cdot\text{edge}^{2}-\left(\frac{1}{2}-\text{edge}\right)\cdot\text{edge}\cdot\text{edge}\right]\ge0. \tag*{(33)} [ ( edge − edge ) 2 edge − edge ⋅ triangle ⋅ edge 2 − ( 2 1 − edge ) ⋅ edge ⋅ edge ] ≥ 0. (33)
By the assumptions of this case, we know ∣ L ( G ) ∣ ≥ ∣ H ( G ) ∣ |L(G)|\ge|H(G)| ∣ L ( G ) ∣ ≥ ∣ H ( G ) ∣ . For any high-degree vertex v v v in G G G we can also say
e ( V ( G ) ∖ N ( v ) ) + n 2 − ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ H ( G ) ) + ( n 2 − ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G ) ) ≥ e ( N ( v ) ∩ H ( G ) ) + n 2 − ∣ N ( v ) ∩ H ( G ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ⋅ e ( N ( v ) ∩ H ( G ) , N ( v ) ∖ H ( G ) ) + ( n 2 − ∣ N ( v ) ∩ H ( G ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G ) ) , (34) \begin{aligned}
e(V(G)\setminus N(v))+
\frac{\frac{n}{2}-|V(G)\setminus N(v)|}{|N(v)\setminus H(G)|}\cdot e(V(G)\setminus N(v),N(v)\setminus H(G))\\
+\left(\frac{\frac{n}{2}-|V(G)\setminus N(v)|}{|N(v)\setminus H(G)|}\right)^2\cdot e(N(v)\setminus H(G))\\
\ge e(N(v)\cap H(G))+
\frac{\frac{n}{2}-|N(v)\cap H(G)|}{|N(v)\setminus H(G)|}\cdot e(N(v)\cap H(G),N(v)\setminus H(G))\\
+\left(\frac{\frac{n}{2}-|N(v)\cap H(G)|}{|N(v)\setminus H(G)|}\right)^2\cdot e(N(v)\setminus H(G)), \tag*{(34)}
\end{aligned} e ( V ( G ) ∖ N ( v )) + ∣ N ( v ) ∖ H ( G ) ∣ 2 n − ∣ V ( G ) ∖ N ( v ) ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ H ( G )) + ( ∣ N ( v ) ∖ H ( G ) ∣ 2 n − ∣ V ( G ) ∖ N ( v ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G )) ≥ e ( N ( v ) ∩ H ( G )) + ∣ N ( v ) ∖ H ( G ) ∣ 2 n − ∣ N ( v ) ∩ H ( G ) ∣ ⋅ e ( N ( v ) ∩ H ( G ) , N ( v ) ∖ H ( G )) + ( ∣ N ( v ) ∖ H ( G ) ∣ 2 n − ∣ N ( v ) ∩ H ( G ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G )) , (34)
as the right side of the inequality represents the number of edges inside a subset of N ( v ) N(v) N ( v ) of size n 2 \frac{n}{2} 2 n . By Mantel’s theorem, this can never exceed n 2 16 \frac{n^2}{16} 16 n 2 , so if the opposite inequality held for any high-degree v v v in G G G , Theorem 4.3 would immediately give a contradiction. As a consequence, we know that for any choice of the red label in W W W
(unlabelled edge) + ( 1 2 − (unlabelled vertex) ) ⋅ (two labelled wedges) ⋅ ( (red–blue wedge) + (red–cyan wedge) ) + ( 1 2 − (unlabelled vertex) ) 2 ( (blue–blue wedge) + (blue–cyan wedge) + (cyan–cyan wedge) ) ≥ (red–red wedge) + ( 1 2 − (red vertex) ) ⋅ (two labelled wedges) ⋅ ( (red–blue wedge) + (red–cyan wedge) ) + ( 1 2 − (red vertex) ) 2 ( (blue–blue wedge) + (blue–cyan wedge) + (cyan–cyan wedge) ) , \begin{aligned}
\text{(unlabelled edge)}+\left(\frac{1}{2}-\text{(unlabelled vertex)}\right)\cdot\text{(two labelled wedges)}\cdot\left(\text{(red--blue wedge)}+\text{(red--cyan wedge)}\right)+\left(\frac{1}{2}-\text{(unlabelled vertex)}\right)^2\left(\text{(blue--blue wedge)}+\text{(blue--cyan wedge)}+\text{(cyan--cyan wedge)}\right) \\
&\geq\text{(red--red wedge)}+\left(\frac{1}{2}-\text{(red vertex)}\right)\cdot\text{(two labelled wedges)}\cdot\left(\text{(red--blue wedge)}+\text{(red--cyan wedge)}\right)+\left(\frac{1}{2}-\text{(red vertex)}\right)^2\left(\text{(blue--blue wedge)}+\text{(blue--cyan wedge)}+\text{(cyan--cyan wedge)}\right),
\end{aligned} (unlabelled edge) + ( 2 1 − (unlabelled vertex) ) ⋅ (two labelled wedges) ⋅ ( (red–blue wedge) + (red–cyan wedge) ) + ( 2 1 − (unlabelled vertex) ) 2 ( (blue–blue wedge) + (blue–cyan wedge) + (cyan–cyan wedge) ) ≥ (red–red wedge) + ( 2 1 − (red vertex) ) ⋅ (two labelled wedges) ⋅ ( (red–blue wedge) + (red–cyan wedge) ) + ( 2 1 − (red vertex) ) 2 ( (blue–blue wedge) + (blue–cyan wedge) + (cyan–cyan wedge) ) ,
which, after basic manipulation and averaging, implies
[ ( unlabelled edge − red–red edge ) ⋅ ( blue wedge + cyan wedge ) 2 + ( 1 2 − unlabelled vertex ) ⋅ ( blue wedge + cyan wedge ) ⋅ ( unlabelled–blue wedge + unlabelled–cyan wedge ) \left[\left(\text{unlabelled edge}-\text{red--red edge}\right)\cdot\left(\text{blue wedge}+\text{cyan wedge}\right)^2+\left(\frac{1}{2}-\text{unlabelled vertex}\right)\cdot\left(\text{blue wedge}+\text{cyan wedge}\right)\cdot\left(\text{unlabelled--blue wedge}+\text{unlabelled--cyan wedge}\right)\right. [ ( unlabelled edge − red–red edge ) ⋅ ( blue wedge + cyan wedge ) 2 + ( 2 1 − unlabelled vertex ) ⋅ ( blue wedge + cyan wedge ) ⋅ ( unlabelled–blue wedge + unlabelled–cyan wedge )
− ( 1 2 − red vertex ) ⋅ ( red–blue wedge + red–cyan wedge ) ⋅ ( red–blue wedge + red–cyan wedge ) + [ ( 1 2 − unlabelled vertex ) 2 − ( 1 2 − red vertex ) 2 ] ⋅ ( blue–blue wedge + blue–cyan wedge + cyan–cyan wedge ) ] ≥ 0. (35) \left.
-\left(\frac{1}{2}-\text{red vertex}\right)\cdot\left(\text{red--blue wedge}+\text{red--cyan wedge}\right)\cdot\left(\text{red--blue wedge}+\text{red--cyan wedge}\right)
+\left[\left(\frac{1}{2}-\text{unlabelled vertex}\right)^2-\left(\frac{1}{2}-\text{red vertex}\right)^2\right]\cdot\left(\text{blue--blue wedge}+\text{blue--cyan wedge}+\text{cyan--cyan wedge}\right)\right]\geq0. \tag*{(35)} − ( 2 1 − red vertex ) ⋅ ( red–blue wedge + red–cyan wedge ) ⋅ ( red–blue wedge + red–cyan wedge ) + [ ( 2 1 − unlabelled vertex ) 2 − ( 2 1 − red vertex ) 2 ] ⋅ ( blue–blue wedge + blue–cyan wedge + cyan–cyan wedge ) ] ≥ 0. (35)
Since D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 5 3 D_{2,\infty}^{b}(G)>0.0671n^2+4n^{\frac{5}{3}} D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 3 5 , we also know that any high-degree vertex satisfies
e ( V ( G ) ∖ N ( v ) ) + n 2 ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ H ( G ) ) + ( n 2 − ∣ V ( G ) ∖ N ( v ) ∣ ∣ N ( v ) ∖ H ( G ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G ) ) ≥ 0.0671 n 2 , (36) \begin{aligned}
e(V(G)\setminus N(v))+\frac{n}{2}\frac{|V(G)\setminus N(v)|}{|N(v)\setminus H(G)|}\cdot e(V(G)\setminus N(v),N(v)\setminus H(G)) \\
&+\left(\frac{\frac{n}{2}-|V(G)\setminus N(v)|}{|N(v)\setminus H(G)|}\right)^2\cdot e(N(v)\setminus H(G))\geq0.0671n^2, \tag*{(36)}
\end{aligned} e ( V ( G ) ∖ N ( v )) + 2 n ∣ N ( v ) ∖ H ( G ) ∣ ∣ V ( G ) ∖ N ( v ) ∣ ⋅ e ( V ( G ) ∖ N ( v ) , N ( v ) ∖ H ( G )) + ( ∣ N ( v ) ∖ H ( G ) ∣ 2 n − ∣ V ( G ) ∖ N ( v ) ∣ ) 2 ⋅ e ( N ( v ) ∖ H ( G )) ≥ 0.0671 n 2 , (36)
which means
[ ( unlabelled edge − 0.1342 ) ⋅ ( blue wedge + cyan wedge ) 2 + ( 1 2 − unlabelled vertex ) ⋅ ( blue wedge + cyan wedge ) ⋅ ( unlabelled–blue wedge + unlabelled–cyan wedge ) \left[\left(\text{unlabelled edge}-0.1342\right)\cdot\left(\text{blue wedge}+\text{cyan wedge}\right)^2+\left(\frac{1}{2}-\text{unlabelled vertex}\right)\cdot\left(\text{blue wedge}+\text{cyan wedge}\right)\cdot\left(\text{unlabelled--blue wedge}+\text{unlabelled--cyan wedge}\right)\right. [ ( unlabelled edge − 0.1342 ) ⋅ ( blue wedge + cyan wedge ) 2 + ( 2 1 − unlabelled vertex ) ⋅ ( blue wedge + cyan wedge ) ⋅ ( unlabelled–blue wedge + unlabelled–cyan wedge )
+ ( 1 2 − unlabelled vertex ) 2 ⋅ ( blue–blue wedge + blue–cyan wedge + cyan–cyan wedge ) ] ≥ 0. (37) \left.
+\left(\frac{1}{2}-\text{unlabelled vertex}\right)^2\cdot\left(\text{blue--blue wedge}+\text{blue--cyan wedge}+\text{cyan--cyan wedge}\right)\right]\geq0. \tag*{(37)} + ( 2 1 − unlabelled vertex ) 2 ⋅ ( blue–blue wedge + blue–cyan wedge + cyan–cyan wedge ) ] ≥ 0. (37)
We now consider the high-degree edge cut. We can reformulate, and average the assumption (14) into the form
[ ( two-vertex graph − two-vertex graph ) ⋅ two-vertex graph + 1 2 ( two-vertex graph − two-vertex graph ) ⋅ two-vertex graph \left[\left(\text{two-vertex graph}-\text{two-vertex graph}\right)\cdot\text{two-vertex graph}
+\frac{1}{2}\left(\text{two-vertex graph}-\text{two-vertex graph}\right)\cdot\text{two-vertex graph}\right. [ ( two-vertex graph − two-vertex graph ) ⋅ two-vertex graph + 2 1 ( two-vertex graph − two-vertex graph ) ⋅ two-vertex graph
+ ( 1 2 − edge indicator − 1 2 edge indicator ) ⋅ two-vertex graph − ( 1 2 − edge indicator − 1 2 edge indicator ) ⋅ two-vertex graph + ( 1 2 edge indicator − 1 2 edge indicator ) ⋅ two-vertex graph ] ≥ 0. (38) \left.
+\left(\frac{1}{2}-\text{edge indicator}-\frac{1}{2}\text{edge indicator}\right)\cdot\text{two-vertex graph}
-\left(\frac{1}{2}-\text{edge indicator}-\frac{1}{2}\text{edge indicator}\right)\cdot\text{two-vertex graph}
+\left(\frac{1}{2}\text{edge indicator}-\frac{1}{2}\text{edge indicator}\right)\cdot\text{two-vertex graph}\right]\geq0. \tag*{(38)} + ( 2 1 − edge indicator − 2 1 edge indicator ) ⋅ two-vertex graph − ( 2 1 − edge indicator − 2 1 edge indicator ) ⋅ two-vertex graph + ( 2 1 edge indicator − 2 1 edge indicator ) ⋅ two-vertex graph ] ≥ 0. (38)
Similarly to the vertex cuts, we can see that D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 5 3 D_{2,\infty}^{b}(G)>0.0671n^2+4n^{\frac{5}{3}} D 2 , ∞ b ( G ) > 0.0671 n 2 + 4 n 3 5 implies
(two-vertex graph) + 1 2 (two-vertex graph) + 1 4 (two-vertex graph) + ( 1 2 − 1 2 ) (two-vertex graph) + ( 1 4 − 1 4 ) (two-vertex graph) + (two-vertex graph) \text{(two-vertex graph)}+\frac{1}{2}\text{(two-vertex graph)}+\frac{1}{4}\text{(two-vertex graph)}+\left(\frac{1}{2}-\frac{1}{2}\right)\text{(two-vertex graph)}+\left(\frac{1}{4}-\frac{1}{4}\right)\text{(two-vertex graph)}+\text{(two-vertex graph)} (two-vertex graph) + 2 1 (two-vertex graph) + 4 1 (two-vertex graph) + ( 2 1 − 2 1 ) (two-vertex graph) + ( 4 1 − 4 1 ) (two-vertex graph) + (two-vertex graph)
≥ 0.0671 ⋅ 2. (39) \geq0.0671\cdot2. \tag*{(39)} ≥ 0.0671 ⋅ 2. (39)
which, after averaging, implies
[ ( first flag expression − 0.1342 ) ⋅ flag expression + ( 1 2 − flag expression − 1 2 flag expression ) ⋅ flag expression + ( 1 4 − 1 2 flag expression − 1 4 flag expression ) ⋅ flag expression ] ≥ 0. (40) \left[\left(\text{first flag expression}-0.1342\right)\cdot\text{flag expression}+\left(\frac{1}{2}-\text{flag expression}-\frac{1}{2}\text{flag expression}\right)\cdot\text{flag expression}+\left(\frac{1}{4}-\frac{1}{2}\text{flag expression}-\frac{1}{4}\text{flag expression}\right)\cdot\text{flag expression}\right]\ge0. \tag*{(40)} [ ( first flag expression − 0.1342 ) ⋅ flag expression + ( 2 1 − flag expression − 2 1 flag expression ) ⋅ flag expression + ( 4 1 − 2 1 flag expression − 4 1 flag expression ) ⋅ flag expression ] ≥ 0. (40)
The degree-cut assumption (26) can be rewritten as
( red edge − red edge ) ⋅ ( blue + cyan ) 2 + ( 1 2 − red ) ⋅ ( blue + cyan ) ⋅ ( red edge + cyan edge ) − ( red − red ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0. (41) (\text{red edge}-\text{red edge})\cdot(\text{blue}+\text{cyan})^2+\left(\frac{1}{2}-\text{red}\right)\cdot(\text{blue}+\text{cyan})\cdot(\text{red edge}+\text{cyan edge})-(\text{red}-\text{red})^2\cdot(\text{blue edge}+\text{blue edge}+\text{cyan edge})\ge0. \tag*{(41)} ( red edge − red edge ) ⋅ ( blue + cyan ) 2 + ( 2 1 − red ) ⋅ ( blue + cyan ) ⋅ ( red edge + cyan edge ) − ( red − red ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0. (41)
It is also clear that the following must hold
red edge + 1 2 − red blue + cyan ⋅ ( red edge + cyan edge ) + ( 1 2 − red blue + cyan ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0.0671 ⋅ 2 , (42) \text{red edge}+\frac{\frac{1}{2}-\text{red}}{\text{blue}+\text{cyan}}\cdot(\text{red edge}+\text{cyan edge})+\left(\frac{\frac{1}{2}-\text{red}}{\text{blue}+\text{cyan}}\right)^2\cdot(\text{blue edge}+\text{blue edge}+\text{cyan edge})\ge0.0671\cdot2, \tag*{(42)} red edge + blue + cyan 2 1 − red ⋅ ( red edge + cyan edge ) + ( blue + cyan 2 1 − red ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0.0671 ⋅ 2 , (42)
which, in the linear form, is
( red edge − 0.1342 ) ⋅ ( blue + cyan ) 2 + ( 1 2 − red ) ⋅ ( blue + cyan ) ⋅ ( red edge + cyan edge ) + ( 1 2 − red ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0. (43) (\text{red edge}-0.1342)\cdot(\text{blue}+\text{cyan})^2+\left(\frac{1}{2}-\text{red}\right)\cdot(\text{blue}+\text{cyan})\cdot(\text{red edge}+\text{cyan edge})+\left(\frac{1}{2}-\text{red}\right)^2\cdot(\text{blue edge}+\text{blue edge}+\text{cyan edge})\ge0. \tag*{(43)} ( red edge − 0.1342 ) ⋅ ( blue + cyan ) 2 + ( 2 1 − red ) ⋅ ( blue + cyan ) ⋅ ( red edge + cyan edge ) + ( 2 1 − red ) 2 ⋅ ( blue edge + blue edge + cyan edge ) ≥ 0. (43)
The globality of this cut implies that no averaging is necessary.
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (17) , (18) , (19) , (20) , (24) , (25) , (29) , (31) , (32) , (33) , (35) , (37) , (38) , (40) , (41) and (43) at once.
This clearly implies that the maximum of expected values of both sides of one of the cuts used in this case for G G G is at most 0.0671 n 2 0.0671n^2 0.0671 n 2 . Assume that the smallest cut is the high-degree edge cut for some edge u v uv uv . Let ( A , B , C , D ) (A,B,C,D) ( A , B , C , D ) be the partition of V ( G ) V(G) V ( G ) defined as ( N ( u ) ∖ N ( v ) , N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( u ) ∪ N ( v ) ) , N ( u ) ∩ N ( v ) ) (N(u)\setminus N(v),N(v)\setminus N(u),V(G)\setminus(N(u)\cup N(v)),N(u)\cap N(v)) ( N ( u ) ∖ N ( v ) , N ( v ) ∖ N ( u ) , V ( G ) ∖ ( N ( u ) ∪ N ( v )) , N ( u ) ∩ N ( v )) . If ∣ C ∣ |C| ∣ C ∣ is odd, we choose any vertex x x x from C C C and apply Theorem 4.4 to ( A ∪ { x } , B , C ∖ { x } , D ) (A\cup\{x\},B,C\setminus\{x\},D) ( A ∪ { x } , B , C ∖ { x } , D ) to get a split ( C 1 , C 2 ) (C_1,C_2) ( C 1 , C 2 ) of C ∖ { x } C\setminus\{x\} C ∖ { x } . Afterwards, we obtain the final partition by applying Theorem 4.3 to ( A ∪ { x } ∪ C 1 , B ∪ C 2 , D ) (A\cup\{x\}\cup C_1,B\cup C_2,D) ( A ∪ { x } ∪ C 1 , B ∪ C 2 , D ) , which can be done as ∣ A ∣ + ∣ C 1 ∣ + 1 ≤ ∣ A ∣ + ∣ C ∣ + 1 2 ≤ ∣ A ∣ + ∣ C ∣ ≤ n 2 |A|+|C_1|+1\le|A|+\frac{|C|+1}{2}\le|A|+|C|\le\frac{n}{2} ∣ A ∣ + ∣ C 1 ∣ + 1 ≤ ∣ A ∣ + 2 ∣ C ∣ + 1 ≤ ∣ A ∣ + ∣ C ∣ ≤ 2 n .
Our manipulations on x x x introduce a slight error:
Edges with at least one endpoint in N ( u , v ) N(u,v) N ( u , v ) are now more likely to end up on the right side of the partition than the formula following Theorem 4.10 indicates. However, the increase of this probability is at most 1 2 ∣ N ( u , v ) ∣ \frac{1}{2|N(u,v)|} 2∣ N ( u , v ) ∣ 1 . Crudely bounding the total number of edges with at least one endpoint in N ( u , v ) N(u,v) N ( u , v ) by n ⋅ ∣ N ( u , v ) ∣ n\cdot|N(u,v)| n ⋅ ∣ N ( u , v ) ∣ , we can bound the total error by n 2 \frac{n}{2} 2 n .
Notice that K 4 K_4 K 4 -freeness implies that there are no edges inside N ( u , v ) N(u,v) N ( u , v ) , which lets us conclude D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + ( 2 + 1 3 + 1 3 + 1 3 ) n 5 3 + n < 0.0671 n 2 + 4 n 5 3 D^b_{2,\infty}(G)\le0.0671n^2+\left(2+\frac{1}{3}+\frac{1}{3}+\frac{1}{3}\right)n^{\frac{5}{3}}+n<0.0671n^2+4n^{\frac{5}{3}} D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + ( 2 + 3 1 + 3 1 + 3 1 ) n 3 5 + n < 0.0671 n 2 + 4 n 3 5 . If ∣ C ∣ |C| ∣ C ∣ is even, an analogous but more straightforward application of Theorem 4.4 and Theorem 4.3 gives the same bound but with a smaller error term. For other cuts, we only need Theorem 4.3, which gives D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + 2 n 5 3 D^{b}_{2,\infty}(G) \le0.0671n^{2}+2n^{\frac{5}{3}} D 2 , ∞ b ( G ) ≤ 0.0671 n 2 + 2 n 3 5 . In either case, we obtain a contradiction, giving a bound of 0.0671 n 2 + 4 n 5 3 0.0671n^{2}+4n^{\frac{5}{3}} 0.0671 n 2 + 4 n 3 5 for even-sized graphs. The extension to odd-sized graphs described at the start of this section increases the error term to 5 n 5 3 5n^{\frac{5}{3}} 5 n 3 5 .
Case 2: This case is almost identical to Case 1, but we consider the opposite relationship for the degree cut. To be precise, we consider K 4 K_{4} K 4 -free graphs that satisfy the following inequalities
∣ L ( G ) ∣ n ≥ 1 2 , \frac{|L(G)|}{n}\ge\frac{1}{2}, n ∣ L ( G ) ∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≥ 0.02 , \frac{e(H(G))}{\binom{n}{2}}\ge0.02, ( 2 n ) e ( H ( G )) ≥ 0.02 ,
and
( n 2 ∣ L ( G ) ∣ ) 2 ⋅ e ( L ( G ) ) ≥ e ( H ( G ) ) + n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ⋅ e ( L ( G ) , H ( G ) ) + ( n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ) 2 ⋅ e ( L ( G ) ) . (44) \left(\frac{\frac{n}{2}}{|L(G)|}\right)^{2}\cdot e(L(G))
\ge e(H(G))+\frac{\frac{n}{2}-|H(G)|}{|L(G)|}\cdot e(L(G),H(G))
+\left(\frac{\frac{n}{2}-|H(G)|}{|L(G)|}\right)^{2}\cdot e(L(G)). \tag*{(44)} ( ∣ L ( G ) ∣ 2 n ) 2 ⋅ e ( L ( G )) ≥ e ( H ( G )) + ∣ L ( G ) ∣ 2 n − ∣ H ( G ) ∣ ⋅ e ( L ( G ) , H ( G )) + ( ∣ L ( G ) ∣ 2 n − ∣ H ( G ) ∣ ) 2 ⋅ e ( L ( G )) . (44)
These conditions have the same implications for W W W as in Case 1, aside from (25), which changes to
( 1 2 blue + cyan ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) ≥ red blue + cyan ⋅ ( blue–red + cyan–red ) + ( 1 2 − red blue + cyan ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) . (45) \left(\frac{\frac{1}{2}}{\text{blue}+\text{cyan}}\right)^{2}
\cdot(\text{blue--blue}+\text{blue--cyan}+\text{cyan--cyan})
\ge
\frac{\text{red}}{\text{blue}+\text{cyan}}\cdot
(\text{blue--red}+\text{cyan--red})
+\left(\frac{\frac{1}{2}-\text{red}}{\text{blue}+\text{cyan}}\right)^{2}
\cdot(\text{blue--blue}+\text{blue--cyan}+\text{cyan--cyan}). \tag*{(45)} ( blue + cyan 2 1 ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) ≥ blue + cyan red ⋅ ( blue–red + cyan–red ) + ( blue + cyan 2 1 − red ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) . (45)
The linear form of (44) is
( red − red 2 ) ⋅ ( blue–blue + blue–cyan + cyan–cyan ) − red ⋅ ( blue + cyan ) 2 − ( 1 2 − red ) ⋅ ( blue + cyan ) ⋅ ( blue–red + cyan–red ) ≥ 0. (46) (\text{red}-\text{red}^{2})\cdot
(\text{blue--blue}+\text{blue--cyan}+\text{cyan--cyan})
-\text{red}\cdot(\text{blue}+\text{cyan})^{2}
-\left(\frac{1}{2}-\text{red}\right)\cdot(\text{blue}+\text{cyan})
\cdot(\text{blue--red}+\text{cyan--red})\ge0. \tag*{(46)} ( red − red 2 ) ⋅ ( blue–blue + blue–cyan + cyan–cyan ) − red ⋅ ( blue + cyan ) 2 − ( 2 1 − red ) ⋅ ( blue + cyan ) ⋅ ( blue–red + cyan–red ) ≥ 0. (46)
By considering the denser side of this cut, we also get
( 1 2 blue + cyan ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) ≥ 0.0671 ⋅ 2 , (47) \left(\frac{\frac{1}{2}}{\text{blue}+\text{cyan}}\right)^{2}
\cdot(\text{blue--blue}+\text{blue--cyan}+\text{cyan--cyan})
\ge0.0671\cdot2, \tag*{(47)} ( blue + cyan 2 1 ) 2 ⋅ ( blue–blue + blue–cyan + cyan–cyan ) ≥ 0.0671 ⋅ 2 , (47)
which is the same as
1 4 ( blue–blue + blue–cyan + cyan–cyan ) − 0.1342 ( blue + cyan ) 2 ≥ 0. (48) \frac{1}{4}(\text{blue--blue}+\text{blue--cyan}+\text{cyan--cyan})
-0.1342(\text{blue}+\text{cyan})^{2}\ge0. \tag*{(48)} 4 1 ( blue–blue + blue–cyan + cyan–cyan ) − 0.1342 ( blue + cyan ) 2 ≥ 0. (48)
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (17), (18), (19), (23), (24), (28), (30), (31), (32), (34), (36), (37), (39), (45) and (47) at once. This implies a contradiction similarly to Case 1.
Case 3: This case is also similar to Case 1, but it differs in which of L ( G ) L(G) L ( G ) and H ( G ) H(G) H ( G ) is larger. The exact set of inequalities which G G G has to satisfy in this case is
∣ H ( G ) ∣ n ≥ 1 2 , (49) \frac{|H(G)|}{n}\ge\frac{1}{2}, \tag*{(49)} n ∣ H ( G ) ∣ ≥ 2 1 , (49)
e ( H ( G ) ) ( n 2 ) ≥ 0.02 , (50) \frac{e(H(G))}{\binom{n}{2}} \ge0.02, \tag*{(50)} ( 2 n ) e ( H ( G )) ≥ 0.02 , (50)
and
e ( L ( G ) ) + n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ⋅ e ( H ( G ) , L ( G ) ) + ( n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) ≥ ( n 2 ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) . (51) \begin{aligned}
e(L(G))+\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\cdot e(H(G),L(G))+\left(\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\right)^2\cdot e(H(G)) \\
&\ge\left(\frac{\frac{n}{2}}{|H(G)|}\right)^2\cdot e(H(G)). \tag*{(51)}
\end{aligned} e ( L ( G )) + ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ⋅ e ( H ( G ) , L ( G )) + ( ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ) 2 ⋅ e ( H ( G )) ≥ ( ∣ H ( G ) ∣ 2 n ) 2 ⋅ e ( H ( G )) . (51)
Clearly, W W W must satisfy
∙ ≥ 1 2 , (52) \bullet\ge\frac{1}{2}, \tag*{(52)} ∙ ≥ 2 1 , (52)
and
(graph expression) ≥ ( 1 2 ) 2 ⋅ (graph expression) . (53) \text{(graph expression)} \ge\left(\frac{1}{2}\right)^2\cdot\text{(graph expression)}. \tag*{(53)} (graph expression) ≥ ( 2 1 ) 2 ⋅ (graph expression) . (53)
A crucial consequence of (52) is that (35) changes to
[ (graph expression) ⋅ (graph expression) 2 + ( 1 2 − (graph expression) ) ⋅ (graph expression) 2 − ( 1 2 − (graph expression) ) ⋅ (graph expression) ⋅ (graph expression) + [ ( 1 2 − (graph expression) ) 2 − ( 1 2 − (graph expression) ) 2 ] ⋅ (graph expression) ] ≥ 0 , (54) \left[\text{(graph expression)}\cdot\text{(graph expression)}^2+\left(\frac{1}{2}-\text{(graph expression)}\right)\cdot\text{(graph expression)}^2-\left(\frac{1}{2}-\text{(graph expression)}\right)\cdot\text{(graph expression)}\cdot\text{(graph expression)}+\left[\left(\frac{1}{2}-\text{(graph expression)}\right)^2-\left(\frac{1}{2}-\text{(graph expression)}\right)^2\right]\cdot\text{(graph expression)}\right]\ge0, \tag*{(54)} [ (graph expression) ⋅ (graph expression) 2 + ( 2 1 − (graph expression) ) ⋅ (graph expression) 2 − ( 2 1 − (graph expression) ) ⋅ (graph expression) ⋅ (graph expression) + [ ( 2 1 − (graph expression) ) 2 − ( 2 1 − (graph expression) ) 2 ] ⋅ (graph expression) ] ≥ 0 , (54)
and (37) changes to
[ ( graph expression − 0.1342 ) ⋅ (graph expression) 2 + ( 1 2 − graph expression ) ⋅ graph expression + ( 1 2 − graph expression ) 2 ⋅ graph expression ] ≥ 0. (55) \left[\left(\text{graph expression}-0.1342\right)\cdot\text{(graph expression)}^2+\left(\frac{1}{2}-\text{graph expression}\right)\cdot\text{graph expression}+\left(\frac{1}{2}-\text{graph expression}\right)^2\cdot\text{graph expression}\right]\ge0. \tag*{(55)} [ ( graph expression − 0.1342 ) ⋅ (graph expression) 2 + ( 2 1 − graph expression ) ⋅ graph expression + ( 2 1 − graph expression ) 2 ⋅ graph expression ] ≥ 0. (55)
In addition, we have to rewrite (41) as
( graph expression ) ⋅ graph expression 2 + ( 1 2 − graph expression ) ⋅ graph expression ⋅ ( graph expression ) − ( graph expression − ( graph expression ) 2 ) ⋅ graph expression ≥ 0 , (56) \left(\text{graph expression}\right)\cdot\text{graph expression}^2+\left(\frac{1}{2}-\text{graph expression}\right)\cdot\text{graph expression}\cdot\left(\text{graph expression}\right)-\left(\text{graph expression}-\left(\text{graph expression}\right)^2\right)\cdot\text{graph expression}\ge0, \tag*{(56)} ( graph expression ) ⋅ graph expression 2 + ( 2 1 − graph expression ) ⋅ graph expression ⋅ ( graph expression ) − ( graph expression − ( graph expression ) 2 ) ⋅ graph expression ≥ 0 , (56)
and (43) as
( graph expression − 0.1342 ) ⋅ graph expression 2 + ( 1 2 − graph expression ) ⋅ graph expression ⋅ ( graph expression ) + ( 1 2 − graph expression ) 2 ⋅ graph expression ≥ 0. (57) \left(\text{graph expression}-0.1342\right)\cdot\text{graph expression}^2+\left(\frac{1}{2}-\text{graph expression}\right)\cdot\text{graph expression}\cdot\left(\text{graph expression}\right)+\left(\frac{1}{2}-\text{graph expression}\right)^2\cdot\text{graph expression}\ge0. \tag*{(57)} ( graph expression − 0.1342 ) ⋅ graph expression 2 + ( 2 1 − graph expression ) ⋅ graph expression ⋅ ( graph expression ) + ( 2 1 − graph expression ) 2 ⋅ graph expression ≥ 0. (57)
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (17) , (18) , (19) , (20) , (52) , (25) , (29) , (31) , (32) , (33) , (53), (54), (37), (39), (55) and (56) at once. This implies a contradiction similarly to Case 1.
Case 4: Case 4 is identical to Case 3 aside from the relationship between sides of the degree cut. Namely, we consider the following set of inequalities:
∣ H ( G ) ∣ n ≥ 1 2 , \frac{\lvert H(G)\rvert}{n} \ge\frac{1}{2}, n ∣ H ( G )∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≥ 0.02 , \frac{e(H(G))}{\binom{n}{2}} \ge0.02, ( 2 n ) e ( H ( G )) ≥ 0.02 ,
and
( n 2 ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) ≥ e ( L ( G ) ) + n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ⋅ e ( H ( G ) , L ( G ) ) + ( n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) . (58) \left(\frac{\frac{n}{2}}{\lvert H(G)\rvert}\right)^2 \cdot e(H(G))
\ge e(L(G))+\frac{\frac{n}{2}-\lvert L(G)\rvert}{\lvert H(G)\rvert}\cdot e(H(G),L(G))+
\left(\frac{\frac{n}{2}-\lvert L(G)\rvert}{\lvert H(G)\rvert}\right)^2\cdot e(H(G)). \tag*{(58)} ( ∣ H ( G )∣ 2 n ) 2 ⋅ e ( H ( G )) ≥ e ( L ( G )) + ∣ H ( G )∣ 2 n − ∣ L ( G )∣ ⋅ e ( H ( G ) , L ( G )) + ( ∣ H ( G )∣ 2 n − ∣ L ( G )∣ ) 2 ⋅ e ( H ( G )) . (58)
Instead of (52), W W W must now satisfy
( 1 2 ∙ ) 2 ⋅ edge ≥ edge + edge + 1 2 − edge + edge ( edge + edge ) + ( 1 2 − edge − edge edge ) 2 ⋅ edge , \left(\frac{\frac{1}{2}}{\bullet}\right)^2\cdot\text{edge}
\ge\text{edge}+\text{edge}+\frac{1}{2}-\text{edge}+\text{edge}
\left(\text{edge}+\text{edge}\right)+
\left(\frac{\frac{1}{2}-\text{edge}-\text{edge}}{\text{edge}}\right)^2\cdot\text{edge}, ( ∙ 2 1 ) 2 ⋅ edge ≥ edge + edge + 2 1 − edge + edge ( edge + edge ) + ( edge 2 1 − edge − edge ) 2 ⋅ edge ,
so (55) changes to
( edge + edge − ( edge + edge ) 2 ) ⋅ edge − ( 1 2 − edge − edge ) ⋅ edge ⋅ ( edge + edge ) ≥ 0. (59) \left(\text{edge}+\text{edge}-\left(\text{edge}+\text{edge}\right)^2\right)\cdot
\text{edge}-\left(\frac{1}{2}-\text{edge}-\text{edge}\right)\cdot
\text{edge}\cdot\left(\text{edge}+\text{edge}\right)\ge0. \tag*{(59)} ( edge + edge − ( edge + edge ) 2 ) ⋅ edge − ( 2 1 − edge − edge ) ⋅ edge ⋅ ( edge + edge ) ≥ 0. (59)
and (56) must change to
1 4 ⋅ edge − 0.1342 ⋅ edge 2 ≥ 0. (60) \frac{1}{4}\cdot\text{edge}-0.1342\cdot\text{edge}^2\ge0. \tag*{(60)} 4 1 ⋅ edge − 0.1342 ⋅ edge 2 ≥ 0. (60)
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (17), (18), (19), (51), (24), (28), (30), (31), (32), (53), (54), (37), (39), (58) and (59) at once. This implies a contradiction similarly to Case 1.
We now consider graphs whose density of high-degree edges is small. Aside from this change, the structure of Cases 5 to 8 mirrors the first four cases.
Case 5: We consider a K 4 K_4 K 4 -free graph G G G that satisfies
∣ L ( G ) ∣ n ≥ 1 2 , \frac{\lvert L(G)\rvert}{n}\ge\frac{1}{2}, n ∣ L ( G )∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≤ 0.02 , (61) \frac{e(H(G))}{\binom{n}{2}}\le0.02, \tag*{(61)} ( 2 n ) e ( H ( G )) ≤ 0.02 , (61)
and
e ( H ( G ) ) + n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ⋅ e ( L ( G ) , H ( G ) ) + ( n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ) 2 ⋅ e ( L ( G ) ) ≥ ( n 2 ∣ L ( G ) ∣ ) 2 ⋅ e ( L ( G ) ) . e(H(G))+\frac{\frac{n}{2}-\lvert H(G)\rvert}{\lvert L(G)\rvert}\cdot e(L(G),H(G))+
\left(\frac{\frac{n}{2}-\lvert H(G)\rvert}{\lvert L(G)\rvert}\right)^2\cdot e(L(G))
\ge
\left(\frac{\frac{n}{2}}{\lvert L(G)\rvert}\right)^2\cdot e(L(G)). e ( H ( G )) + ∣ L ( G )∣ 2 n − ∣ H ( G )∣ ⋅ e ( L ( G ) , H ( G )) + ( ∣ L ( G )∣ 2 n − ∣ H ( G )∣ ) 2 ⋅ e ( L ( G )) ≥ ( ∣ L ( G )∣ 2 n ) 2 ⋅ e ( L ( G )) .
Now, by R R R we denote the low-degree (rather than high-degree) edge cut oriented variant of G G G . Analogously, W W W is the limit of the infinite sequence of increasing blowups of R R R . The most important implication of this change is that the low-degree vertex cut and the high-degree edge cut are no longer relevant. However, we can now use the low-degree edge cut. The analogue of (37) for the low-degree edge cut is
[ ( diagram − diagram ) ⋅ ( diagram + diagram ) 2 + ( 1 2 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) − ( 1 2 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) + [ ( 1 2 − diagram ) 2 − ( 1 2 − diagram ) 2 ] ⋅ ( diagram + diagram ) ] ≥ 0 , (62) \left[\left(\text{diagram}-\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)^2
+\left(\frac{1}{2}-\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)
-\left(\frac{1}{2}-\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)
+\left[\left(\frac{1}{2}-\text{diagram}\right)^2-\left(\frac{1}{2}-\text{diagram}\right)^2\right]\cdot\left(\text{diagram}+\text{diagram}\right)\right]\geq0, \tag*{(62)} [ ( diagram − diagram ) ⋅ ( diagram + diagram ) 2 + ( 2 1 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) − ( 2 1 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) + [ ( 2 1 − diagram ) 2 − ( 2 1 − diagram ) 2 ] ⋅ ( diagram + diagram ) ] ≥ 0 , (62)
while the equivalent of (39) is
[ ( diagram − 0.1342 ) ⋅ ( diagram + diagram ) 2 + ( 1 2 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) + ( 1 2 − diagram ) 2 ⋅ ( diagram + diagram ) ] ≥ 0. (63) \left[\left(\text{diagram}-0.1342\right)\cdot\left(\text{diagram}+\text{diagram}\right)^2
+\left(\frac{1}{2}-\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)\cdot\left(\text{diagram}+\text{diagram}\right)
+\left(\frac{1}{2}-\text{diagram}\right)^2\cdot\left(\text{diagram}+\text{diagram}\right)\right]\geq0. \tag*{(63)} [ ( diagram − 0.1342 ) ⋅ ( diagram + diagram ) 2 + ( 2 1 − diagram ) ⋅ ( diagram + diagram ) ⋅ ( diagram + diagram ) + ( 2 1 − diagram ) 2 ⋅ ( diagram + diagram ) ] ≥ 0. (63)
Condition (60) implies
(diagram) ≤ 0.02. (64) \text{(diagram)}\leq0.02. \tag*{(64)} (diagram) ≤ 0.02. (64)
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (18), (19), (23), (63), (34), (36), (61), (62), (40) and (42) at once. This implies a contradiction similarly to Case 1.
Case 6: In this case, we analyze a K 4 K_4 K 4 -free graph G G G that satisfies
∣ L ( G ) ∣ n ≥ 1 2 , \frac{\lvert L(G)\rvert}{n}\geq\frac{1}{2}, n ∣ L ( G )∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≤ 0.02 , \frac{e(H(G))}{\binom{n}{2}}\leq0.02, ( 2 n ) e ( H ( G )) ≤ 0.02 ,
and
( n 2 ∣ L ( G ) ∣ ) 2 e ( L ( G ) ) ≥ e ( H ( G ) ) + n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ⋅ e ( L ( G ) , H ( G ) ) + ( n 2 − ∣ H ( G ) ∣ ∣ L ( G ) ∣ ) 2 ⋅ e ( L ( G ) ) . \left(\frac{\frac{n}{2}}{\lvert L(G)\rvert}\right)^2e(L(G))
\geq e(H(G))+\frac{\frac{n}{2}-\lvert H(G)\rvert}{\lvert L(G)\rvert}\cdot e(L(G),H(G))
+\left(\frac{\frac{n}{2}-\lvert H(G)\rvert}{\lvert L(G)\rvert}\right)^2\cdot e(L(G)). ( ∣ L ( G )∣ 2 n ) 2 e ( L ( G )) ≥ e ( H ( G )) + ∣ L ( G )∣ 2 n − ∣ H ( G )∣ ⋅ e ( L ( G ) , H ( G )) + ( ∣ L ( G )∣ 2 n − ∣ H ( G )∣ ) 2 ⋅ e ( L ( G )) .
We have already defined all linear inequalities that are necessary to prove a contradiction in this case.
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (18), (19), (23), (63), (34), (36), (61), (62), (45) and (47) at once. This implies a contradiction similarly to Case 1.
Case 7: The exact set of inequalities which G G G has to satisfy in this case is
∣ H ( G ) ∣ n ≥ 1 2 , \frac{|H(G)|}{n} \ge\frac{1}{2}, n ∣ H ( G ) ∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≤ 0.02 , \frac{e(H(G))}{\binom{n}{2}} \le0.02, ( 2 n ) e ( H ( G )) ≤ 0.02 ,
and
e ( L ( G ) ) + n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ⋅ e ( H ( G ) , L ( G ) ) + ( n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) ≥ ( n 2 ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) . e(L(G))+\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\cdot e(H(G),L(G))+\left(\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\right)^2\cdot e(H(G))
\ge\left(\frac{\frac{n}{2}}{|H(G)|}\right)^2\cdot e(H(G)). e ( L ( G )) + ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ⋅ e ( H ( G ) , L ( G )) + ( ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ) 2 ⋅ e ( H ( G )) ≥ ( ∣ H ( G ) ∣ 2 n ) 2 ⋅ e ( H ( G )) .
We have already defined all linear inequalities that are necessary to prove a contradiction in this case.
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (18), (19), (51), (63), (53), (54), (61), (62), (55) and (56) at once. This implies a contradiction similarly to Case 1.
Case 8: Here, we consider the following set of inequalities:
∣ H ( G ) ∣ n ≥ 1 2 , \frac{|H(G)|}{n} \ge\frac{1}{2}, n ∣ H ( G ) ∣ ≥ 2 1 ,
e ( H ( G ) ) ( n 2 ) ≤ 0.02 , \frac{e(H(G))}{\binom{n}{2}} \le0.02, ( 2 n ) e ( H ( G )) ≤ 0.02 ,
and
( n 2 ∣ H ( G ) ∣ ) 2 e ( H ( G ) ) ≥ e ( L ( G ) ) + n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ⋅ e ( H ( G ) , L ( G ) ) + ( n 2 − ∣ L ( G ) ∣ ∣ H ( G ) ∣ ) 2 ⋅ e ( H ( G ) ) . \left(\frac{\frac{n}{2}}{|H(G)|}\right)^2 e(H(G))
\ge e(L(G))+\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\cdot e(H(G),L(G))+\left(\frac{\frac{n}{2}-|L(G)|}{|H(G)|}\right)^2\cdot e(H(G)). ( ∣ H ( G ) ∣ 2 n ) 2 e ( H ( G )) ≥ e ( L ( G )) + ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ⋅ e ( H ( G ) , L ( G )) + ( ∣ H ( G ) ∣ 2 n − ∣ L ( G ) ∣ ) 2 ⋅ e ( H ( G )) .
We have already defined all linear inequalities that are necessary to prove a contradiction in this case.
Calculations at https://github.com/ignacy123/dense-half-k4-free-flags show that no graphon can satisfy all of (16), (18), (19), (51), (63), (53), (54), (61), (62), (58) and (59) at once. This implies a contradiction similarly to Case 1.
Acknowledgements
The computer-assisted part of this work is based on the flag program originally developed by Bernard Lidický (which was used in [5 ] ). The authors are grateful to him for permission to modify the program and to publish the modified version.
AI statement
The results in this paper have been obtained without AI assistance. The paper itself has also been written fully by the authors. The authors have utilized large language models for linguistic checks and a final correctness check. Some minor suggestions from AI for the paper itself and related computer-assisted calculations have been implemented.