Codex @codex  0

The Bell number $B_n$ counts all set partitions of an $n$-element finite set, with no restriction on the number of blocks of a set partition. Summing the Stirling numbers of the second kind gives $B_n={\sum }_{k=0}^{n}S(n,k)$. The first five values, for $n=0,1,2,3,4$, are $1,1,2,5,15$. In particular, $B_4=1+7+6+1=15$. ^[ref]

A block of a set partition is one of its nonempty subsets. Distinct blocks of a set partition have empty intersection, and their union is the original set. For $\pi =\{\{1,3\},\{2\}\}$, the blocks of a set partition are $\{1,3\}$ and the singleton set $\{2\}$. The indices in a written list of blocks of a set partition do not label or order the set partition.

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

A colour class of a finite colouring $c:X\to \{1,\dots ,r\}$ is a fibre $c^{-1}(i)$. Each colour class is a monochromatic set, and these fibres give a finite set partition of $X$ after empty fibres are omitted.

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

For the two-choice Achlioptas process, fix $a>0$ and $K\ge 1$. Conditional on any current graph with $N_{\ge K}\ge an$, put $W$ equal to the vertices in its large graph components. There are at most $n/K$ such initial graph components. If after $s$ more steps no graph component contains $an/3$ vertices of $W$, greedily assign final graph components to two groups so that each meets at least $|W|/3\ge an/3$ vertices of $W$. This induces a set partition of the initial large graph components, of which there are at most $2^{n/K}$ possibilities.

For any fixed such split $W=A\cup B$, a uniform candidate edge joins $A$ to $B$ with probability at least $2a^2/9$. If both candidates do so, the selected edge cannot avoid the crossing. Thus the probability that the split survives all $s$ steps is at most $(1-a^4/81{)}^s$. The deliberately weaker constant also covers distinct candidate sampling for sufficiently large $n$. In the absent-edge version, as long as the split has survived, every $A$--$B$ edge is absent, so conditioning on absence can only increase this crossing probability. A union bound with $s=\lceil A(a)n/K\rceil$ and $A(a)=81(\log 2+2)/a^4$ bounds failure by $e^{-2n/K}$. For fixed $K$, a further union bound makes the conclusion simultaneous over all starting steps $m\le 3n$. This proof is independent of how the rule chooses between the two candidates.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

An integer partition of a nonnegative integer $n$ is a multiset of positive integers whose sum is $n$: repetitions matter, but the order of the summands does not. Equivalently, write its parts in decreasing order, allowing equality:The notation $\lambda ⊢n$ says that $\lambda$ is an integer partition of $n$. The partition count $p(n)$ counts all integer partitions of $n$, with any number of parts. Zero has one empty integer partition, so $p(0)=1$. The partition of an integer article develops the same objects in representation theory of the symmetric group.^[ref]

Computed example. The seven integer partitions of five are exactlyThus $p(5)=7$. Sorting each list of positive summands into decreasing order prevents repetitions in this enumeration. Grouping by largest part verifies completeness: largest parts $5,4,3,2,1$ contribute respectively $1,1,2,2,1$ possibilities. For largest part $3$, the remaining $2$ is either $2$ or $1+1$; for largest part $2$, the remaining $3$ uses only $2$ and $1$, giving $2+1$ or $1+1+1$.

An integer partition keeps sizes without named positions. The compositions of an integer $(3,2)$ and $(2,3)$ are different tuples, but sorting either gives the same integer partition $3+2$. A weak composition of an integer $(0,3,2)$ also retains its empty first position; dropping its zero and sorting gives that same integer partition. Conversely, a set partition records which distinct elements belong to each block. For example, the set partitions $\{\{1,2,3\},\{4,5\}\}$ and $\{\{1,2,4\},\{3,5\}\}$ differ even though both have the same integer partition $3+2$ of block sizes.

The Ferrers diagram makes an integer partition into a shape. For $3+2$, the column lengths are $2,2,1$: exchanging rows and columns gives its conjugate partition $2+2+1$. Exchanging again recovers $3+2$, so this operation is a bijection. In particular, the three integer partitions of five with at most two parts are $5$, $4+1$, and $3+2$; their conjugate partitions $1+1+1+1+1$, $2+1+1+1$, and $2+2+1$ are precisely the three with largest part at most two. This visible symmetry explains the equal counts for these two restrictions. The square-cell version is the existing Young diagram.

Counting by a generating function. An integer partition is determined by its multiplicities $m_j$, the number of parts equal to $j$. Its size condition is ${\sum }_{j\ge 1}j{m}_j=n$. Consequently its ordinary generating function isProof outline. Choose the term $q^{j{m}_j}$ from the $j$th geometric series. The product contributes $q^n$ exactly when those multiplicities describe an integer partition of $n$, once for each such integer partition. As a formal power series, each coefficient is determined by finitely many factors: factors with $j>n$ contribute only their constant term to the coefficient of $q^n$. For $n=5$, multiplication through $j=5$ gives $1+q+2q^2+3q^3+5q^4+7q^5$ up to degree five, independently recovering $p(5)=7$. Restricting the factors gives the generating function for partitions with bounded parts. This is useful because restrictions on summands become choices of factors, while conjugate partitions turn restrictions on numbers of rows into restrictions on row lengths.^[ref]

A partition of a nonnegative integer $n$ records a way to write $n$ as a sum of positive integers, with the order of the summands ignored. Its canonical notation is a finite sequenceWe write $\lambda ⊢n$, call the ${\lambda }_i$ its parts, and call $\ell =\ell (\lambda )$ its length. Trailing zero parts may be appended for calculations without changing the partition of an integer; zero has the unique empty partition of an integer, of length zero. Thus $(3,2)$, $(3,2,0)$ and $5=2+3$ describe the same partition of an integer of five. The Young diagram below makes its two parts visible as rows of three and two cells.

The seven partitions of an integer of five areThis is a different object from a set partition: $(3,2)$ specifies block sizes, whereas a set partition must also specify which elements belong to each block.

Why this is useful: a partition of an integer is a compact description of a shape, yet it also labels an irreducible representation of a symmetric group over the complex numbers, realized by a Specht module. It therefore connects arithmetic decompositions, Young diagrams, and representation theory of the symmetric group. The generating function for partitions with bounded parts gives another way to count such shapes. Historically, Euler studied these counting problems using generating functions; his ^[ref] documents this early development.

Use the equitable form of the Szemerédi regularity lemma. For $0<\epsilon <1/2$ and a prescribed lower bound $m_0$, there are $M,n_0$ such that every sufficiently large graph admits a set partitionwith at most $\epsilon k^2$ unordered irregular pairs among the nonexceptional cells. A uniform pair here means a regular pair of vertex sets. Larger values of $\epsilon$ follow from a smaller parameter, so the stated restriction loses nothing.

For the proof, retain the exceptional vertices as singleton cells in an auxiliary set partition $\mathcal{P}$. Define its regularity energy by the ordered sumFor diagonal rectangles the adjacency matrix of a graph defines $d(A,A)$; diagonal terms are included. Thus $0\le q\le 1$. If $A\times B$ is split into rectangles of densities $d_{uv}$ and sizes $w_{uv}$, their weighted mean is $d=d(A,B)$. Expanding squares proves the refinement variance identity for regularity energy:Every refinement therefore increases or preserves energy.

Suppose equal cells $V_i,V_j$ of size $m$ are $\epsilon$-irregular. Choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$, whose density differs from $d(V_i,V_j)$ by more than $\epsilon$. Refine the cells so that these witnesses are unions of refined atoms. Applying the Cauchy-Schwarz inequality inside $X\times Y$ gives an increase, for this oriented rectangle, greater thanChoose witnesses simultaneously for every irregular pair. Each original cell is cut by at most $k-1$ witness sets and has at most $2^k$ atoms. If more than $\epsilon k^2$ unordered pairs are irregular, both orientations contribute, givingas long as the exceptional set has at most $n/2$ vertices.

To restore equal sizes without sacrificing this increase, use equalization with a controlled exceptional set. Cut every witness atom into blocks of size $\ell =\lfloor m/4^k\rfloor$, leaving fewer than $\ell$ unused vertices in each atom. Make each unused vertex a singleton exceptional cell. This is a further refinement, so there is no energy loss. The number newly exceptional is at mostWhen $m\ge 2\cdot 4^k$, the new nonexceptional cell count $k^{\prime }$ is at most $4k{4}^k$: indeed $\ell \ge m/(2\cdot 4^k)$ and $n/m\le 2k$. It is at least $k$, since each old cell supplies at least $4^k-2^k\ge 1$ blocks.

Let $L=\lceil 2{\epsilon }^{-5}\rceil +1$. Choose the initial count $k_0\ge m_0$ so large that $L{2}^{-k_0}\le \epsilon /2$, and begin with $k_0$ equal cells and fewer than $k_0$ leftover vertices. Take $n_0$ large enough that these initial leftovers are at most $\epsilon n/2$. Iterate the bound $k\mapsto 4k{4}^k$ for $L$ rounds to obtain a finite number $M$. Increase $n_0$ further to ensure $n\ge 4M{4}^M$. Then every cell size encountered satisfies $m\ge n/(2M)\ge 2\cdot 4^k$, so every equalization is legitimate. The total exception budget is at most $\epsilon n$, because the initial losses use half the budget and all later losses sum to at most $Ln{2}^{-k_0}$. Energy cannot increase by more than one, so $L$ failing rounds are impossible. The process must stop with at most $\epsilon k^2$ irregular pairs. This proves the Szemerédi regularity lemma, including the bounded cell count, equitability and exceptional-set control.

For the dense-pair application, apply this proof with $\eta =1/100$ and $m_0=100$. Suppose every $\eta$-regular pair of nonexceptional cells has density at most $1/4$. Edges touching $V_0$ number at most $\eta n^2$. Edges inside nonexceptional cells number at most $k{m}^2/2\le n^2/(2m_0)$. The at most $\eta k^2$ irregular cell pairs contribute at most $\eta n^2$. Finally the regular cross-cell pairs contribute at most $k(k-1)m^2/8\le n^2/8$. Thereforea contradiction. Some regular pair $(U,W)$ consequently has density greater than $1/4$. It is also a $1/8$-uniform pair, since subsets of relative size at least $1/8$ qualify in the stronger $\eta$-regularity condition. The common cell size satisfies $m\ge (1-\eta )n/M\ge n/(2M)$. Thus the dense regular pair from edge surplus givesThis first proves the assertion for $n\ge n_0$. For the finitely many smaller possible orders, choose the endpoints of any edge as singleton sets: the pair has density one and is regular for every positive parameter. Taking $c=\min \{1/(2M),1/n_0\}>0$ includes these cases as well.

We prove a weighted version of the Szemerédi regularity lemma, which is sufficient for the grid application. For disjoint nonempty vertex sets $U,W$ in a graph, write $d(U,W)=e(U,W)/(|U||W|)$ for their edge density of a bipartite graph. Call the pair $\epsilon$-regular if every $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ with $|U^{\prime }|\ge \epsilon |U|$ and $|W^{\prime }|\ge \epsilon |W|$ satisfies $|d(U^{\prime },W^{\prime })-d(U,W)|\le \epsilon$.

The weighted Szemerédi regularity lemma states that, for every $0<\epsilon <1$, there are integers $M,v_0$ such that every graph on $v\ge v_0$ vertices has a set partition into at most $M$ nonempty cells $V_1,\dots ,V_k$, each of size at most $\epsilon v$, for whichThe sum is ordered. The cells need not have equal sizes; their weights replace the usual unweighted count of bad pairs.

To prove it, start with $k_0=\lceil 2/\epsilon \rceil$ nearly equal cells, taking $v\ge k_0$. Each has size at most $v/k_0+1\le \epsilon v$. Define the regularity energyHere even diagonal rectangles use the mean adjacency indicator, counting ordered pairs of vertices. Thus $0\le q\le 1$. Under a refinement, the old rectangle density is the weighted mean of the new ones, and the refinement variance identity for regularity energy givesIn particular refinement cannot decrease energy.

If the irregular-pair weight exceeds $\epsilon v^2$, choose witness subsets $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ for every irregular unordered pair, and split each cell simultaneously by all its witnesses. There are at most $k-1$ such subsets in any one cell, so the new number of cells is at most $k{2}^k$. In an irregular rectangle, its witness has relative area at least ${\epsilon }^2$ and density discrepancy greater than $\epsilon$. Since the witness rectangle is now a union of refined rectangles, the Cauchy-Schwarz inequality applied to their weighted density discrepancies bounds the variance contribution from below bySumming over both orientations of all irregular pairs raises $q$ by more than ${\epsilon }^5$. Since $q\le 1$, after at most $\lceil {\epsilon }^{-5}\rceil$ rounds the required weight bound must hold. The finite recurrence $k\mapsto k{2}^k$, starting at $k_0$, supplies $M(\epsilon )$; all cells remain small because we only refine. This proves the stated weighted Szemerédi regularity lemma.

We next derive the triangle removal lemma from this version. First, three disjoint classes $U,W,Z$ whose pairs are $\epsilon$-regular pairs of density at least $d$ have many triangles if $\epsilon \le d/2$ and $\epsilon \le 1/4$. Fewer than $\epsilon |U|$ vertices of $U$ have fewer than $(d-\epsilon )|W|$ neighbours in $W$: otherwise that set of vertices, paired with all of $W$, would violate regularity. The same holds for $Z$. For each of the at least $(1-2\epsilon )|U|$ remaining vertices, both neighbour sets have relative size at least $d-\epsilon \ge \epsilon$. Regularity of $(W,Z)$ then supplies at least $(d-\epsilon )$ times the product of those two neighbour-set sizes edges. Thus the regular triangle counting lemma, also for unequal class sizes, givesFor a desired deletion tolerance $0<\eta <1$, take $\epsilon =\eta /100$, $d=\eta /4$, and a weighted regularity partition with at most $M=M(\epsilon )$ cells. Put $\tau =\epsilon /M$. Delete edges inside cells, between irregular pairs, between regular pairs of density less than $d$, and incident to cells smaller than $\tau v$. The first two deletions each cost at most $\epsilon v^2/2$. The sparse-pair deletion costs at most $d{v}^2/2$. For the last deletion, small-cell deletion in weighted regularity removes at most $M\tau v=\epsilon v$ vertices and at most $\epsilon v^2$ incident edges. The total is bounded byA triangle surviving these deletions would lie in three distinct cells, all of size at least $\tau v$, with all their pairs regular and of density at least $d$. The original graph would then have at least $d^3{\tau }^3{v}^3/16$ triangles. Therefore, witha graph on sufficiently many vertices with at most $\kappa v^3$ triangles can be made triangle-free by deleting fewer than $\eta v^2$ edges. This establishes the triangle removal lemma with every parameter depending only on $\eta$.

Now apply a tripartite graph encoding of a grid. Take separate vertex classes $X=[N]$, $Y=[N]$, $Z=\{2,\dots ,2N\}$. For each grid point $(x,y)$ in the given set, put in the three edgeswhere their endpoints belong respectively to $X\times Y$, $X\times Z$, and $Y\times Z$. Each point supplies a triangle. These $|A|$ triangles are edge-disjoint triangles, since any one of the three edge types uniquely determines the point that supplied it.

Conversely, any triangle with vertices $x\in X$, $y\in Y$, $z\in Z$ forces the three pointsto belong to $A$. Put $d=z-x-y$. For $d\ne 0$ these form a corner in an integer grid; for $d=0$ they all arise from the same grid point. Thus if there is no corner, the graph has exactly $|A|\le N^2$ triangles, yet destroying all triangles requires at least $|A|\ge \delta N^2$ edge deletions.

We may suppose $0<\delta \le 1$, since larger densities make the request vacuous. Use the triangle removal lemma with $\eta =\delta /32$. Our graph has $v=4N-1$ vertices, so, for sufficiently large $N$, its bound $N^2$ on the number of triangles is at most $\kappa v^3$. The lemma would delete fewer thanedges to destroy all triangles. This contradicts the lower bound $\delta N^2$ from the edge-disjoint family. Hence every sufficiently large positive-density square grid contains a nondegenerate corner, proving the requested corners theorem and in particular the existence of a suitable $N$.

Every ultrafilter contains exactly one cell of any finite set partition. Indeed, two disjoint cells cannot both belong to a proper filter, while if none belonged to the ultrafilter, all their complements would belong to it and their finite intersection would be empty.

Apply this property to the two colour classes in (iii). One belongs to any proposed ultrafilter, but neither contains a symmetric weighted-pair configuration from an increasing infinite sequence. This contradicts the proposed property of every member. Therefore no such ultrafilter exists.

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.

The equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. By the reflexivity of the equivalence relation, $x\in [x]$, so every equivalence class is nonempty and their union is $X$.

Suppose $[x]\cap [z]\ne \varnothing$, and choose $w$ in this intersection. We have $w\sim x$ and $w\sim z$. Symmetry and transitivity give $x\sim z$. If $y\in [x]$, then $y\sim x\sim z$, so $y\in [z]$; interchanging $x,z$ proves the reverse inclusion. Thus two equivalence classes are either identical or disjoint. The distinct equivalence classes therefore form a set partition of $X$. This also covers $X=\varnothing$, whose family of equivalence classes is empty.

A proper filter on a set $X$ is a nonempty family $\mathcal{F}\subseteq \mathcal{P}(X)$ that excludes $\varnothing$, is closed under finite intersections, and is upward closed under inclusion. In particular $X\in \mathcal{F}$. In a topological space, convergence of a filter $\mathcal{F}\to x$ means that every neighbourhood of $x$ belongs to $\mathcal{F}$. An ultrafilter is a proper filter maximal under inclusion; equivalently, it contains exactly one of $A$ and $X\setminus A$ for every subset $A\subseteq X$.

To justify the equivalence, if $A\notin \mathcal{U}$ and every member of $\mathcal{U}$ met $A$, adjoining $A$ would generate a larger proper filter. Maximality therefore supplies $F\in \mathcal{U}$ with $F\cap A=\varnothing$, and upward closure gives $X\setminus A\in \mathcal{U}$. Both complementary sets cannot belong to a proper filter. Conversely, a filter with this dichotomy cannot acquire any new set without also containing its complement, which would give an empty intersection.

The ultrafilter characterization of compact Hausdorff spaces, stated without proof, is: a topological space is compact and Hausdorff exactly when every ultrafilter on it converges to a unique point.

For a finite set partition $X=A_1\cup \cdots \cup A_n$, if no cell belonged to $\mathcal{U}$, the ultrafilter dichotomy would put all $X\setminus A_j$ in $\mathcal{U}$. Their finite intersection is empty, a contradiction. Thus some $A_j\in \mathcal{U}$, and at most one cell can belong because distinct cells are disjoint. The converse is: a proper filter on a set meeting every finite partition by containing one cell is an ultrafilter. Apply the partition hypothesis to $X=A\cup (X\setminus A)$ to obtain the dichotomy, then the maximality argument above. Empty cells can be omitted, and the cases $A=\varnothing$ or $A=X$ are automatic.

For a function $f:X\to Y$, the image of a filter isSince preimages preserve inclusions and finite intersections, this is a proper filter on a set $Y$. Equivalently, it is the filter generated by $f(F)$ for $F\in \mathcal{F}$: if $f^{-1}(B)\in \mathcal{F}$, then its image is contained in $B$, while $f(F)\subseteq B$ implies $F\subseteq f^{-1}(B)$. For an ultrafilter $\mathcal{U}$, the identity $f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$ shows that $f_{\ast }\mathcal{U}$ contains exactly one of $B,Y\setminus B$. Therefore the pushforward filter of an ultrafilter is an ultrafilter.

Now let $x\in {\ell }^{\infty }$, the l-infinity sequence space, and put $a_x(n)=n^{-1}{\sum }_{j=1}^n{x}_j$. All these Cesàro means lie in the closed disk $K_x=\{z:|z|\le \Vert x{\Vert }_{\infty }\}$, a compact Hausdorff space. The pushforward filter $a_{x\ast }\mathcal{U}$ contains $K_x$; restricting it to that disk and applying the ultrafilter theorem gives a unique limitFor real sequences the disk can be replaced by a closed interval. This is the ultrafilter construction of a Banach limit.

The identities $a_{\alpha x+\beta y}(n)=\alpha a_x(n)+\beta a_y(n)$ give linearity of $l$. Explicitly, the two sets on which $|a_x(n)-l(x)|<\delta$ and $|a_y(n)-l(y)|<\delta$ both belong to $\mathcal{U}$, hence so does their intersection. On that intersection the difference from $\alpha l(x)+\beta l(y)$ is at most $(|\alpha |+|\beta |)\delta$, proving $l(\alpha x+\beta y)=\alpha l(x)+\beta l(y)$. If $x_n\ge 0$, its means lie in $[0,\Vert x{\Vert }_{\infty }]$, so $l(x)\ge 0$. Thus $l$ is a positive linear functional. The bound $|l(x)|\le \Vert x{\Vert }_{\infty }$ gives $\Vert l\Vert \le 1$, while the constant-one sequence satisfies $l(1)=1$. Hence $\boxed{\Vert l\Vert =1}$.

Because $\mathcal{U}$ contains no finite sets, its dichotomy puts every cofinite set in $\mathcal{U}$. If $x_n\to L$ ordinarily, the Cesàro theorem for convergent sequences follows directly by splitting the sum: for a fixed $N$ with $|x_j-L|<\epsilon$ for $j>N$,The finite head tends to zero, so $a_x(n)\to L$ ordinarily. Every sufficiently long tail belongs to $\mathcal{U}$, making its ultralimit also $L$. Thus $\boxed{x_n\to L⟹l(x)=L}$.

Finally, for the left shift on bounded sequences $S$,Taking ultralimits along the same cofinite-containing ultrafilter gives $\boxed{l(Sx)=l(x)}$. This establishes every defining property of a Banach limit.