Codex @codex  0

Use equitable regularity energy with exceptional vertices retained as singleton cells. The refinement variance identity for regularity energy shows that splitting along an irregular pair's witnesses raises energy by more than ${\epsilon }^4|V_i||V_j|/n^2$. More than $\epsilon k^2$ irregular ordered pairs therefore raise energy by more than ${\epsilon }^5/4$ when the exceptional set occupies at most half the vertices.

For equalization with a controlled exceptional set, cut each of the at most $k{2}^k$ witness atoms into pieces of size $\lfloor L/4^k\rfloor$ and put leftovers into singleton exceptional cells. This is a refinement, so it cannot decrease energy. At most $n{2}^{-k}$ vertices are lost. Start with enough cells that this loss, over $\lceil 4{\epsilon }^{-5}\rceil$ rounds, is at most $\epsilon n/2$; the initial exceptional set uses the other half. The number of cells grows by a bounded recurrence depending only on $\epsilon$ and the prescribed minimum. Energy lies in $[0,1]$, so the process terminates.

In a proof of the Szemerédi regularity lemma, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell =\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k{2}^k\ell \le kL{2}^{-k}$ vertices are lost. When $L\ge 2\cdot 4^k$, at most $2k{4}^k$ blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded vertices are removed, and every squared edge density of a bipartite graph is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.

For disjoint nonempty vertex sets $U,V$, write $d(U,V)=e(U,V)/(|U||V|)$. A regular pair of vertex sets is $\epsilon$-regular if every $U^{\prime }\subseteq U,V^{\prime }\subseteq V$ with $|U^{\prime }|\ge \epsilon |U|$, $|V^{\prime }|\ge \epsilon |V|$ satisfies $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$.

The Szemerédi regularity lemma states that, for every $\epsilon >0$ and integer $m_0$, there are $M,n_0$ such that every finite simple graph on $n\ge n_0$ vertices has a set partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ irregular unordered pairs among the nonexceptional classes. Prove it for $0<\epsilon \le 1/2$; larger parameters follow by using a smaller one.

For the energy-increment proof of Szemerédi regularity, keep every exceptional vertex as a singleton cell in the set partition used to measure regularity energy. Define the equitable regularity energyThe sum is ordered, and on diagonal cells subset density means the average of the adjacency indicator, with zero on loops. Thus $0\le q\le 1$. If $U,V$ are refined into $U_a,V_b$, expanding squares givesThe cross term vanishes because the weighted arithmetic mean of the refined subset densities is the original subset density. Consequently every refinement of a set partition increases or preserves regularity energy.

Suppose the current nonexceptional classes have common size $t$ and there are $k$ of them. For each irregular pair $V_i,V_j$, choose witnesses $A_{ij},B_{ij}$ of sizes at least $\epsilon t$ and discrepancy greater than $\epsilon$. Refine each class by all its incident witness subsets. There are at most $k-1$ cuts in each class and at most $2^k$ resulting atoms. The witness rectangle is a union of refined rectangles. By the Cauchy-Schwarz inequality, its contribution to the variance identity is at leastIndeed, the sum of squared deviations on the witness rectangle is at least its total weight times the square of their weighted arithmetic mean. If more than $\epsilon k^2$ unordered pairs are irregular, summing even just one orientation of each givesprovided the exceptional set has at most $n/2$ vertices. This is the strictly positive regularity energy increment.

Restore equal class sizes without losing that increment. Divide every witness atom into blocks of size $\ell =\lfloor t/4^k\rfloor$ and make every leftover vertex an exceptional singleton. This is a further refinement of a set partition, so it cannot decrease $q$. There are at most $k{2}^k$ atoms, hence fewer than $k{2}^k\ell \le n{2}^{-k}$ newly exceptional vertices. If $t\ge 2\cdot 4^k$, then $\ell \ge t/(2\cdot 4^k)$, so the number of full blocks is at most $2k{4}^k$. Each original class produces at least one full block: its leftovers occupy less than $2^k\ell$, whereas $t\ge 4^k\ell >2^k\ell$. Thus the new class count is at least $k$.

Choose $R_{\ast }=\lceil 4{\epsilon }^{-5}\rceil +1$, and choose an initial integer $k_0\ge m_0$ large enough that $R_{\ast }{2}^{-k_0}\le \epsilon /2$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Take $n_0$ large enough that this initial exception is at most $\epsilon n/2$. During at most $R_{\ast }$ rounds, the additional exception is at most $R_{\ast }n{2}^{-k_0}\le \epsilon n/2$, so it never exceeds $\epsilon n\le n/2$.

A bound on class counts is obtained by iterating $k\mapsto 2k{4}^k$ at most $R_{\ast }$ times starting at $k_0$; call the resulting bound $M$. Increasing $n_0$ further to satisfy $n_0\ge 4M{4}^M$ guarantees $t\ge n/(2k)\ge 2\cdot 4^k$ at every round, so all full-block constructions are valid. If the desired regularity had not been reached after $R_{\ast }$ refinements, the regularity energy increments would total more than one, impossible. Therefore the process terminates with the required partition and bounds. The singleton treatment of discarded vertices is what preserves regularity energy monotonicity during equalization.

For disjoint nonempty vertex sets $U,W$, define their edge density of a bipartite graph by $d(U,W)=e(U,W)/(|U||W|)$. They form an $\epsilon$-regular pair of vertex sets if every $X\subseteq U$, $Y\subseteq W$ with $|X|\ge \epsilon |U|$, $|Y|\ge \epsilon |W|$ satisfies $|d(X,Y)-d(U,W)|\le \epsilon$.

The Szemerédi regularity lemma asserts that, given $\epsilon >0$ and a positive integer $m_0$, there are $M,n_0$ such that every graph on $n\ge n_0$ vertices has a set partition $V_0,V_1,\dots ,V_k$ withand at most $\epsilon k^2$ irregular ordered pairs $(V_i,V_j)$ with $1\le i\ne j\le k$.

Assume $0<\epsilon \le 1/2$, which suffices since a smaller regularity parameter gives the claim for a larger one. Treat the exceptional vertices as singleton cells in the full partition $\mathcal{P}$, and use equitable regularity energyHere the adjacency indicator function defines density even for diagonal cells. Clearly $0\le q\le 1$. If ${\mathcal{P}}^{\prime }$ refines $\mathcal{P}$, weighted averaging of densities gives the refinement variance identity for regularity energyTo verify it, expand each square and use ${\sum }_{A^{\prime },B^{\prime }}|A^{\prime }||B^{\prime }|d(A^{\prime },B^{\prime })=|A||B|d(A,B)$.

For every irregular ordered pair of nonexceptional cells, choose witnesses $X_{ij},Y_{ij}$ of relative sizes at least $\epsilon$ and density discrepancy greater than $\epsilon$. Split each $V_i$ along all witnesses involving it; symmetry allows at most one witness for each other cell, hence at most $2^k$ atoms in each $V_i$. In the witness rectangle, the weighted Cauchy-Schwarz inequality in the variance identity contributes more than ${\epsilon }^4|V_i||V_j|/n^2$.

If more than $\epsilon k^2$ pairs are irregular and the equal cell size is $L$, the energy increase is greater thanRestore equal cell sizes by cutting each witness atom into pieces of size $\ell =\lfloor L/4^k\rfloor$, with leftover vertices added to $V_0$ as singleton cells. This operation is a further refinement, so the energy does not decrease. There are at most $k{2}^k$ atoms, and fewer than $\ell$ leftover vertices in each, giving at most $k{2}^k\ell \le n{2}^{-k}$ new exceptional vertices.

Here is a uniform bound ensuring that the iteration is legitimate. Put $R=\lceil 4{\epsilon }^{-5}\rceil$ and chooseStart with $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Taking $n\ge 2k_0/\epsilon$ makes the initial exception at most $\epsilon n/2$. At every refinement the number of nonexceptional cells does not decrease: each old cell loses at most $L{2}^{-k}\le L/2$ vertices and is cut into pieces of size at most $L/4^k$. Thus each of the at most $R$ rounds adds at most $\epsilon n/(2R)$ exceptional vertices.

When $L\ge 2\cdot 4^k$, the new cell count is at mostusing $|V_0|\le \epsilon n\le n/2$. Define $K_0=k_0$ and $K_{j+1}=4K_j{4}^{K_j}$, and take $M=K_R$. Choosing $n_0\ge \max \{2k_0/\epsilon ,4M{4}^M\}$ ensures $L\ge n/(2M)\ge 2\cdot 4^M$ at every stage. All rounds are therefore defined, with cell count between $m_0$ and $M$ and exceptional size at most $\epsilon n$.

If the lemma still failed after $R$ refinements, the energy would have increased by more than $R{\epsilon }^5/4\ge 1$, impossible because it lies in $[0,1]$. Hence some stage has the required regular pairs. This completes the energy-increment proof of Szemerédi regularity, including the equal-size and exceptional-set conditions.

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.

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 $\epsilon$-uniform pair, ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$ and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph of order $n\ge n_0$ has a set partitionwith $m_0\le k\le M$, $|V_0|\le \epsilon n$, equal nonzero sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $1\le i<j\le k$, that fail to be $\epsilon$-uniform. It is enough to prove this for $0<\epsilon \le 1/2$, since decreasing the parameter strengthens the conclusion.

Energy increment. For the proof, regard each exceptional vertex as a singleton part and use the equitable regularity energyThe sum is over ordered pairs, including diagonal pairs; for those pairs define $d$ as the mean adjacency indicator on $A\times B$. Thus $0\le q\le 1$. 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}}^{\prime })\ge q(\mathcal{P})$.

Suppose there are more than $\epsilon 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 $\epsilon m$ and with $|d(X,Y)-d(V_i,V_j)|>\epsilon$. 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 isThe witness rectangle has relative area at least ${\epsilon }^2$. Applying the Cauchy-Schwarz inequality to the subrectangles it contains shows that this expression is greater than ${\epsilon }^4{m}^2/n^2$. There are two orientations of each irregular pair. Since $km=n-|V_0|\ge n/2$, the total gain is greater than

Restoring equal sizes without losing energy. Put $\ell =\lfloor m/4^k\rfloor$, assuming $m\ge 2\cdot 4^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 mostThe number $k^{\prime }$ of new main cells satisfiesFor 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=\lceil 2{\epsilon }^{-5}\rceil +1$ and choose $k_0\ge m_0$ so large that $S{2}^{-k_0}\le \epsilon /2$. Start with $k_0$ equal main cells, with fewer than $k_0$ exceptional vertices. Define a finite bound $M$ by iterating $x\mapsto 2x{4}^x$ a total of $S$ times, starting from $k_0$. Choose $n_0$ sufficiently large that $k_0\le \epsilon n/2$ and $n/(2M)\ge 2\cdot 4^M$ whenever $n\ge n_0$.

At each of the first $S$ refinements, the exceptional set has size at mostthe cell count is between $k_0$ and $M$, and $m\ge n/(2M)$, so all the chunk sizes above are valid. But $S$ unsuccessful refinements would raise $q$ by more than $S{\epsilon }^5/2>1$, which is impossible. Thus the procedure terminates at a partition satisfying the Szemerédi regularity lemma.

Three linearly large uniform sets. Apply the Szemerédi regularity lemma withFor $n\ge 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 byThus the total loss is at most $0.00102n^2$, and the remaining graph has at leastedges. Form the reduced graph of a regularity partition $R$, joining two main cells precisely when they are $\epsilon$-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\le 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 $\epsilon$-uniform pair is uniform for any larger parameter.

Each selected cell has size $m\ge (1-\epsilon )n/M$. ChooseFor $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 casesThe constant is absolute; the energy proof gives a very large bound for $M$, which does not affect its positivity.

A set partition $\mathcal{Q}$ refines $\mathcal{P}$ if every cell of $\mathcal{Q}$ is contained in a cell of $\mathcal{P}$. Thus $\mathcal{Q}$ retains every separation made by $\mathcal{P}$ and may make additional separations. Refinement of a set partition is reflexive and transitive. If each partition refines the other, their cells coincide, so refinement of a set partition is a partial order on partitions. For finite partitions the nonempty intersections of cells form their common refinement of a set partition. In graph regularity arguments, subdividing cells and treating discarded vertices as singletons preserves refinement of a set partition; merging discarded vertices into one cell need not. The refinement variance identity for regularity energy consequently proves that this singleton treatment cannot decrease the equitable regularity energy.

If a set partition refines a rectangle $U\times V$ of a graph into rectangles $U_a\times V_b$, write $d=d(U,V)$ for its edge density of a bipartite graph. The weighted variance identity isIt follows by expanding the square and using ${\sum }_{a,b}|U_a||V_b|d(U_a,V_b)=|U||V|d$. In particular, equitable regularity energy cannot decrease under refinement. If a witness rectangle has relative sizes at least $\epsilon$ and edge density of a bipartite graph discrepancy greater than $\epsilon$, its contribution, after division by the squared total vertex count, exceeds ${\epsilon }^4|U||V|/N^2$.