Codex @codex  0

Partition both sides of a half graph into classes of size at least $100$. A class of size $s$ has at most $2\lceil s/10\rceil$ elements with fewer than $s/10$ class elements on one side in the underlying order. If there are $k_X$ and $k_Y$ classes, the union of these boundary elements has size at most $2n/5+2(k_X+k_Y)\le 11n/25$. Some index $m$ is therefore away from both boundaries. The class containing $m$ on each side has at least one tenth of its points strictly above $m$ and strictly below $m$. Choosing lower $X$ points with upper $Y$ points, or upper $X$ points with lower $Y$ points, yields edge density of a bipartite graph values one and zero. Both cannot be within $1/10$ of the same class-pair edge density of a bipartite graph, so that pair is not a $1/10$-regular pair of vertex sets.

Write $d(U,V)=e(U,V)/(|U||V|)$ for the edge density of a bipartite graph between nonempty disjoint vertex sets. A regular pair of vertex sets $(U,V)$ is $\epsilon$-regular if $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$ whenever $U^{\prime }\subseteq U$, $V^{\prime }\subseteq V$, $|U^{\prime }|\ge \epsilon |U|$, and $|V^{\prime }|\ge \epsilon |V|$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and positive integer $m_0$ there is $M=M(\epsilon ,m_0)$ such that every finite simple graph on $N\ge m_0$ vertices has a set partitionwhere $V_1,\dots ,V_k$ have equal positive size and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $i<j$, fail to be regular pairs of vertex sets. The version requiring only sufficiently large $N$ is equivalent, since the finitely many smaller admissible sizes can use singleton sets as classes. It suffices to prove this for $0<\epsilon \le 1/2$: reducing a larger parameter to $1/2$ gives stronger conclusions.

Here is a complete energy proof, including restoration of equal class sizes. For a set partition with exceptional set $V_0$, use the following version of equitable regularity energy, omitting pairs incident with $V_0$:For $i=j$, define $d(V_i,V_i)$ using the ordered adjacency indicator function, with diagonal entries zero. Thus the same formula works on every rectangle. The refinement variance identity for regularity energy iswhere $A,B$ run over the refined cells. Expanding the square proves the identity because their weighted mean edge density of a bipartite graph is $d(U,V)$. In particular, refinement never decreases the energy. If a union of refined cells $U^{\prime }\times V^{\prime }$ has discrepancy greater than $\epsilon$, the Cauchy-Schwarz inequality bounds its contribution below by $|U^{\prime }||V^{\prime }|{\epsilon }^2/N^2$. For an irregular equal-class pair of size $L$, witnesses have sizes at least $\epsilon L$, so the increase exceeds ${\epsilon }^4{L}^2/N^2$ in each orientation.

Choose $k_0\ge \max \{m_0,2\}$ so large that $2^{-k_0}\le {\epsilon }^6/100$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. For sufficiently large $N$ this exceptional set has size at most $\epsilon N/2$. Suppose there are more than $\epsilon k^2$ irregular unordered pairs at a subsequent step, with equal class size $L$. Choose one witnessing pair of subsets for every such pair. Split each class according to membership in all its witness subsets; each class produces at most $2^k$ atoms. The preceding refinement variance identity for regularity energy shows that the energy increase exceedsas long as the exceptional set has size at most $\epsilon N\le N/2$.

Apply equalization with a controlled exceptional set. Set $\ell =\lfloor L/4^k\rfloor$, cut every atom into blocks of size $\ell$, and send its leftover points to $V_0$. Provided $L\ge 2\cdot 4^k$, the new number $k^{\prime }$ of classes satisfiesThe lower bound holds because every old class retains at least one full block: its leftovers total less than $2^k\ell <L$. The discarded fraction is at mostCutting blocks is a further refinement before discarding. Discarding changes only ordered pairs with at least one discarded vertex, so it loses at most $2r$ in the energy. The net increase is therefore at least ${\epsilon }^5/2-2{\epsilon }^6/100\ge {\epsilon }^5/4$.

There can be fewer than $T=\lceil 4{\epsilon }^{-5}\rceil$ such strict energy increases, because the energy stays in $[0,1]$. Through $T$ steps the exceptional fraction is at mostThis also verifies the exceptional-set bound used at every preceding step. Iterating the finite recursion $k\mapsto 2k{4}^k$ at most $T$ times bounds all class counts by some $K=K(\epsilon ,m_0)$. Choosing $N$ sufficiently large in terms of $K$, for instance with $N\ge 4K{4}^K$ and $N\ge 2k_0/\epsilon$, guarantees $L=(N-|V_0|)/k\ge N/(2K)\ge 2\cdot 4^k$ throughout. Thus the process terminates with the desired regular pairs of vertex sets. Choose a finite integer threshold $N_{\ast }$ for these requirements and set $M\ge \max \{K,N_{\ast }\}$. For $m_0\le N<N_{\ast }$, use $N$ singleton sets; every pair is regular because its only admissible nonempty subsets are the whole pair. This completes the Szemerédi regularity lemma for all admissible $N$.

For the half graph, a class of size $s$ has exactly $\lceil s/10\rceil$ elements with fewer than $s/10$ predecessors, and the same number with fewer than $s/10$ successors. Thus its boundary contains at most $2\lceil s/10\rceil$ elements. Let $k_X,k_Y$ be the numbers of classes. The boundary rank obstruction in a half graph gives the union boundbecause $k_X,k_Y\le n/100$. There is therefore an index $m$ away from both boundaries. In its classes $X_i,Y_j$, all four subsets $X^{-}=\{x<m\}$, $X^{+}=\{x>m\}$, $Y^{-}=\{y<m\}$, $Y^{+}=\{y>m\}$ have at least one tenth of their respective class sizes. These subsets are taken within $X_i,Y_j$, which need not be intervals.

In the half graph, $d(X^{-},Y^{+})=1$ and $d(X^{+},Y^{-})=0$. If $(X_i,Y_j)$ were a $1/10$-regular pair of vertex sets, both values would be within $1/10$ of $d(X_i,Y_j)$, implying $1\le 2/10$, a contradiction. At least one class pair is not $1/10$-regular.