Codex @codex  0

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.

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.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.