= Solution
\b[Statement and definitions.] For disjoint nonempty sets $A,B$ of <vertices>, their <edge density of a bipartite graph> is $d(A,B)=e(A,B)/(|A||B|)$. They form a <regular pair of vertex sets>, or an $\varepsilon$-uniform pair, if
$$
|d(X,Y)-d(A,B)|\leq\varepsilon
$$
whenever $X\subseteq A$, $Y\subseteq B$, $|X|\geq\varepsilon|A|$ and $|Y|\geq\varepsilon|B|$.
The <Szemerédi regularity lemma> states that for every $\varepsilon>0$ and positive integer $m_0$, there are integers $M,n_0$ such that every <graph> of order $n\geq n_0$ has a <set partition>
$$
V(G)=V_0\sqcup V_1\sqcup\cdots\sqcup V_k
$$
with $m_0\leq k\leq M$, $|V_0|\leq\varepsilon n$, equal nonzero sizes $|V_1|=\cdots=|V_k|$, and at most $\varepsilon k^2$ unordered pairs $(V_i,V_j)$, $1\leq i<j\leq k$, that fail to be $\varepsilon$-uniform. It is enough to prove this for $0<\varepsilon\leq1/2$, since decreasing the parameter strengthens the conclusion.
\b[Energy increment.] For the proof, regard each exceptional <vertex> as a singleton part and use the <equitable regularity energy>
$$
q(\mathcal P)=\frac1{n^2}\sum_{A,B\in\mathcal P}|A||B|d(A,B)^2.
$$
The sum is over ordered pairs, including diagonal pairs; for those pairs define $d$ as the mean adjacency indicator on $A\times B$. Thus $0\leq q\leq1$. Under a refinement, the subrectangle densities have the original density as their weighted mean. The <Cauchy-Schwarz inequality>, equivalently the nonnegativity of their weighted <variance>, gives $q(\mathcal P')\geq q(\mathcal P)$.
Suppose there are more than $\varepsilon k^2$ irregular pairs, with main cell size $m$. For each such pair choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\varepsilon m$ and with $|d(X,Y)-d(V_i,V_j)|>\varepsilon$. Refine every main cell by all its witness subsets. Each splits into at most $2^{k-1}$ atoms, and we may use the larger bound $2^k$.
For an ordered irregular rectangle, write its refined densities as $d_{ab}$ and relative areas as $w_{ab}$. The energy gain on that rectangle is
$$
\frac{m^2}{n^2}\sum_{a,b}w_{ab}(d_{ab}-d(V_i,V_j))^2.
$$
The witness rectangle has relative area at least $\varepsilon^2$. Applying the <Cauchy-Schwarz inequality> to the subrectangles it contains shows that this expression is greater than $\varepsilon^4m^2/n^2$. There are two orientations of each irregular pair. Since $km=n-|V_0|\geq n/2$, the total gain is greater than
$$
2\varepsilon^5\frac{k^2m^2}{n^2}\geq\varepsilon^5/2.
$$
\b[Restoring equal sizes without losing energy.] Put $\ell=\lfloor m/4^k\rfloor$, assuming $m\geq2\cdot4^k$. Split every refined atom into sets of size $\ell$, putting its leftover fewer than $\ell$ <vertices> into the exceptional set as singleton parts. This is a further refinement, so the energy cannot decrease. The number of new exceptional <vertices> is at most
$$
k2^k\ell\leq km/2^k\leq n/2^k.
$$
The number $k'$ of new main cells satisfies
$$
k\leq k'\leq\frac{km}{\ell}\leq2k4^k.
$$
For the first inequality, in each old cell the leftovers have total size less than $2^k\ell<m$, so at least one full chunk survives. All previous exceptional singleton parts are kept. Treating leftovers as singleton parts is what makes the energy increment survive equitabilization exactly.
Take $S=\lceil2\varepsilon^{-5}\rceil+1$ and choose $k_0\geq m_0$ so large that $S2^{-k_0}\leq\varepsilon/2$. Start with $k_0$ equal main cells, with fewer than $k_0$ exceptional <vertices>. Define a finite bound $M$ by iterating $x\mapsto2x4^x$ a total of $S$ times, starting from $k_0$. Choose $n_0$ sufficiently large that $k_0\leq\varepsilon n/2$ and $n/(2M)\geq2\cdot4^M$ whenever $n\geq n_0$.
At each of the first $S$ refinements, the exceptional set has size at most
$$
k_0+S n2^{-k_0}\leq\varepsilon n,
$$
the cell count is between $k_0$ and $M$, and $m\geq n/(2M)$, so all the chunk sizes above are valid. But $S$ unsuccessful refinements would raise $q$ by more than $S\varepsilon^5/2>1$, which is impossible. Thus the procedure terminates at a partition satisfying the <Szemerédi regularity lemma>.
\b[Three linearly large uniform sets.] Apply the <Szemerédi regularity lemma> with
$$
\varepsilon=10^{-5},\qquad m_0=1000,\qquad d_0=10^{-3}.
$$
For $n\geq n_0$, delete all <edges> touching $V_0$, all internal main-cell <edges>, all <edges> of irregular pairs, and all <edges> of regular pairs whose <edge density of a bipartite graph> is less than $d_0$. The respective losses are bounded by
$$
\varepsilon n^2,\qquad \frac{n^2}{2m_0},\qquad \varepsilon n^2,\qquad \frac{d_0n^2}{2}.
$$
Thus the total loss is at most $0.00102n^2$, and the remaining <graph> has at least
$$
(0.255-0.00102)n^2=0.25398n^2>n^2/4
$$
<edges>. Form the <reduced graph of a regularity partition> $R$, joining two main cells precisely when they are $\varepsilon$-uniform and have <edge density of a bipartite graph> at least $d_0$. If their common size is $m$, the remaining <edge> count is at most $e(R)m^2$. Since $km\leq n$, we obtain $e(R)>k^2/4$. The <Mantel theorem> gives a <triangle in a graph> in $R$. Its three cells $U_1,U_2,U_3$ have the required pairwise density and are $10^{-3}$-uniform: an $\varepsilon$-uniform pair is uniform for any larger parameter.
Each selected cell has size $m\geq(1-\varepsilon)n/M$. Choose
$$
c=\min\left\{\frac{1-\varepsilon}{2M},\frac1{n_0}\right\}>0.
$$
For $n<n_0$, the <Mantel theorem> gives a <triangle in a graph> in the original <graph>, since its <edge> count exceeds $n^2/4$; take its three singleton <vertices>. Their pairs have density one and are uniform for every positive parameter, and $1>cn$. Therefore in all cases
$$
\boxed{|U_i|>cn,\quad (U_i,U_j)\text{ is }10^{-3}\text{-uniform},\quad d(U_i,U_j)\geq10^{-3}.}
$$
The constant is absolute; the energy proof gives a very large bound for $M$, which does not affect its positivity.
Back to article page
