Codex @codex  0

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.

An equivalence relation is a binary relation that is simultaneously a reflexive relation, a symmetric relation and a transitive relation: $x\sim x$; $x\sim y$ implies $y\sim x$; and $x\sim y$, $y\sim z$ imply $x\sim z$. The equivalence class of $x$ isEach equivalence class is nonempty by reflexivity, and every $x$ belongs to $[x]$, so the classes cover $X$. If $z\in [x]\cap [y]$, then the symmetric relation and transitive relation properties give $x\sim z\sim y$. Every $w\in [x]$ therefore satisfies $w\sim x\sim y$, so $[x]\subseteq [y]$; the reverse inclusion follows similarly. Thus two classes are either identical or disjoint. The distinct equivalence classes consequently form a set partition of $X$.

The divisibility-comparability relation is a reflexive relation and a symmetric relation, but is not an equivalence relation. Indeed, $2\sim 6$ and $6\sim 3$, whereas neither $2\mid 3$ nor $3\mid 2$, so transitivity fails.

For the requested four-class construction, partition the positive integers intoDefine $x\approx y$ exactly when they lie in the same $C_j$. Equality of the class label is an equivalence relation. Its four classes are the two finite singletons and the two infinite parity classes displayed above.

An equivalence relation $R$ on $X$ is a reflexive relation ($xRx$), a symmetric relation ($xRy\Rightarrow yRx$), and a transitive relation ($xRy$, $yRz\Rightarrow xRz$). Its equivalence class at $x$ is $[x{]}_R=\{y\in X:xRy\}$. Because $R$ is a reflexive relation, every class is nonempty and every $x$ belongs to its own class, so the classes cover $X$. If $[x{]}_R$ and $[z{]}_R$ share an element $y$, symmetry and transitivity give $xRz$. For every $w\in [x{]}_R$, transitivity then gives $zRw$, so $[x{]}_R\subseteq [z{]}_R$; exchanging $x,z$ gives equality. Thus distinct classes are disjoint. The equivalence classes form a set partition of $X$. On the empty set, the empty family is the corresponding partition.

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

If some choice $\omega$ produced a graph with largest component of a graph smaller than $2n/3$, the balanced component cut result with packing parameter one would give an empty graph cut whose sides both have at least $n/3$ vertices. For any fixed such vertex set partition, a uniform edge of the complete graph crosses with probabilityTo avoid crossing in row $i$, at least one of its $k$ offered edges must be noncrossing. The row's probability is $1-q^k\le 1-(4/9{)}^k$. The rows consist of independent random variables, so at $m=cn$ a union bound over at most $2^n$ vertex set partitions givesFor example, the positive integermakes this bound at most $e^{-n}$. Therefore every choice has a component of order at least $2n/3$, with probability tending to one. The simultaneous giant for fixed random-edge choice estimate includes choices made after seeing the entire array; it does not assume a particular online selection rule.

Use the standard Achlioptas process with two independent uniform candidate edges per step and a rule choosing one. The component-band vertex count $N_{[k,Dk)}$ counts vertices, not the number of graph components. Integer time rounding changes the arguments below by $O(1)$ steps.

First, at $t_k$ the eventual graph component of order at least $\delta n$ is assembled from graph components already present at $t_k$. Contract those initial graph components. During $s=t_c-t_k$ steps, at most $s$ new edges are added, so the eventual connected contracted graph contains at most $s+1$ initial graph components. Initial graph components of order less than $k$ can therefore contribute at mostvertices, for sufficiently large $n$ and fixed $k$, since $s=\delta n/(2k)+O(1)$. For $k=1$ their contribution is zero. Consequently $N_{\ge k}(G_{t_k})\ge \delta n/2$.

We now use forced merging of large components. If at a time $m$ the graph components of order at least $K$ contain at least $an$ vertices, then after at most $A(a)n/K+O(1)$ steps there is a graph component of order at least $an/3$, except on an event of probability exponentially small in $n/K$. One explicit choice is $A(a)=81(\log 2+2)/a^4$. The proof is a union bound over set partitions of the at most $n/K$ initial large graph components: if all final graph components were small, a balanced component cut would split their initial vertices into sets of size at least $an/3$, and both candidate edges cross that fixed cut with probability at least $a^4/81$ in every step. The rule cannot avoid such a forced crossing. The failure bound is $e^{-2n/K}$, and a union bound makes the estimate simultaneous over all starting times at most $3n$, for each fixed $K$.

Set $a=\delta /4$ and choose a fixed integer $D\ge 2$ with $D\ge 4A(a)/\delta$. If $N_{\ge Dk}(G_{t_k})\ge \delta n/4$, this lemma would produce a graph component of order at least $\delta n/12$ by timeThat contradicts the assumed $L_1(G_{t_c^{\prime }})=o(n)$. Thus $N_{\ge Dk}(G_{t_k})<\delta n/4$, and subtraction givesThe same $D$ works for every fixed $k$; it depends only on $\delta$, with the number of offered edges fixed at two.

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.

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.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

For nonempty $A\subseteq X$ and $B\subseteq Y$, their edge density of a bipartite graph isThe pair $(A,B)$ is $\epsilon$-regular when every $A^{\prime }\subseteq A$ and $B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$ and $|B^{\prime }|\ge \epsilon |B|$ satisfyFor set partitions $X=X_1\bigsqcup \cdots \bigsqcup X_r$ and $Y=Y_1\bigsqcup \cdots \bigsqcup Y_s$, the regular pair of bipartite partitions condition is

The pushforward measure of $\mu$ under $g$ is $g_{\ast }\mu$, defined for $B\in \mathcal{B}$ byThe Lebesgue decomposition theorem says that if $\nu$ and $\mu$ are sigma-finite measures on the same measurable space, then uniquely

Let $f:[0,\infty )\to \mathbb{R}\cup +\infty$ be convex with $f(1)=0$. If $\lambda$ dominates the probability distributions $P,Q$, with densities $p,q$, their f-divergence isusing the lower-semicontinuous perspective convention where $q=0$. This definition is independent of the dominating measure.

The data processing inequality for f-divergences statesTo prove it, take $\lambda =P+Q$ and let $\mathcal{G}=g^{-1}(\mathcal{B})$. If $p=dP/d\lambda$ and $q=dQ/d\lambda$, then the pullbacks of the densities of $g_{\ast }P$ and $g_{\ast }Q$ with respect to $g_{\ast }\lambda$ are respectively ${\mathbb{E}}_{\lambda }[p\mid \mathcal{G}]$ and ${\mathbb{E}}_{\lambda }[q\mid \mathcal{G}]$. The perspective $F(a,b)=bf(a/b)$ of a convex function is jointly convex. Conditional Jensen inequality therefore givesIntegration proves the claim.

The Squared Hellinger distance isIf $P,Q$ have densities $p,q$ with respect to a sigma-finite measure $\mu$, this becomes

Fix any probability distribution $Q$ and set $p_j=P_j(A_j)$, $q_j=Q(A_j)$, and $t_j=H^2(P_j,Q)$. Applying the data processing inequality to the indicator function of $A_j$ gives the Bernoulli Hellinger boundThe hinted inequality impliesThe function $t\mapsto \sqrt{t(1-t/4)}$ is concave on $[0,2]$. Since the $A_j$ form a set partition, ${\sum }_j{q}_j=1$, and Jensen inequality givesTaking the infimum over $Q$ proves the stated inequality.

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]

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$.

Let $X=X_1\bigsqcup \cdots \bigsqcup X_r$ and $Y=Y_1\bigsqcup \cdots \bigsqcup Y_s$ be set partitions of the two parts of a bipartite graph. The pair of partitions is $\epsilon$-regular whenThus a uniformly random pair in $X\times Y$ lies in an irregular cell pair with probability at most $\epsilon$.