Codex @codex  0

Write $X=[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, and $[M{]}^{\omega }$ for all infinite subsets of an infinite $M$. A family $Y\subseteq X$ is a Ramsey set of infinite subsets if for every infinite $M$ there is an infinite $L\subseteq M$ with either $[L{]}^{\omega }\subseteq Y$ or $[L{]}^{\omega }\cap Y=\varnothing$.

A non-Ramsey set of infinite subsets is obtained by finite-symmetric-difference parity colouring. Declare $A\sim B$ when their symmetric difference is finite, and use the axiom of choice to select a representative $R$ for each equivalence class. PutFor every infinite $L$, both $L$ and $L\setminus \{\min L\}$ belong to $[L{]}^{\omega }$ and have the same representative. Toggling one element changes the parity of the finite symmetric difference, so these two sets have opposite colors. Thus no $[L{]}^{\omega }$ is homogeneous, and $Y$ is not a Ramsey set of infinite subsets. Only finite differences are counted; no parity is being assigned to an infinite cardinal.

We use the Ellentuck topology for the star notation. Its basic neighborhoods arewhere $s$ is a finite stem (the initial segment of each member of the neighborhood) and every element of the infinite reservoir $A$ exceeds $\max s$; the empty stem is allowed. A star-nowhere dense set $N$ has star-closure with empty star-interior; a star-meagre set is a countable union of star-nowhere dense sets.

We need the following stem-preserving open-set conclusion: a star-open set $G$ has, in every $[s,A]$, an infinite $B\subseteq A$ such that $[s,B]\subseteq G$ or $[s,B]\cap G=\varnothing$. Here is the fusion proof for open Ellentuck sets, so that the precise form being used is explicit. A reservoir $T$ accepts a finite extension $t$ of $s$ when $[t,T]\subseteq G$, and rejects it when no infinite subreservoir accepts it. Every reservoir can be thinned to decide a prescribed stem: take an accepting subreservoir if one exists, and otherwise it already rejects. Acceptance and rejection are hereditary under further infinite thinning.

First thin $A$ to decide $s$. If it accepts, we have finished. Otherwise, choose successive points $b_0<b_1<\cdots$, thinning the unused tail after each selection to decide every stem $s\cup t$ with $t$ a subset of the finitely many points already selected. Each stage requires only finitely many decisions. The final set $B$ therefore decides every such finite extension, using the tail above its largest point. It rejects $s$.

For any rejected stem $s\cup t$, only finitely many possible next points $b$ of $B$ have accepting tails for $s\cup t\cup \{b\}$. Otherwise collect infinitely many such points into $C$. Every member of $[s\cup t,C]$ starts with some such $b$, and its remaining points lie in the accepting tail above $b$. Hence $[s\cup t,C]\subseteq G$, contradicting rejection. A second selection now gives $C\subseteq B$ all of whose finite extensions of $s$ are rejected: at each stage avoid the finitely many forbidden next points for each subset of the chosen prefix. Previous rejections persist on thinning. If $Z\in [s,C]\cap G$, star-openness gives an initial stem $s\cup t$ of $Z$ and an infinite tail of $Z$ whose entire neighborhood lies in $G$. This is an accepting subreservoir for a stem we made rejected, a contradiction. Thus $[s,C]\cap G=\varnothing$, proving the needed open-set conclusion.

Apply this conclusion to $G=X\setminus {\overline{N}}^{\ast }$ when $N$ is star-nowhere dense. This $G$ is star-open and star-dense. The alternative $[s,B]\cap G=\varnothing$ would give a nonempty star-open set inside ${\overline{N}}^{\ast }$, contradicting empty interior. Consequently every star-nowhere dense set can be avoided without extending the finite stem.

Now let $N={\bigcup }_{j\ge 0}{N}_j$, each $N_j$ star-nowhere dense, and fix $[s,A]$. Construct $b_0<b_1<\cdots$ with nested infinite unused reservoirs. At stage $j$, let $P_j=\{b_0,\dots ,b_{j-1}\}$. For every $t\subseteq P_j$, in turn, thin the current reservoir using the preceding avoidance property untilThere are only finitely many such $t$, and subsequent thinning preserves all previous avoidances. Choose $b_j=\min C_j$ and retain the part of $C_j$ above $b_j$ for the next stage. Put $B=\{b_j:j\ge 0\}$. For any $Z\in [s,B]$ and any $j$, the finite part $t=(Z\setminus s)\cap P_j$ is one of the stems tested at stage $j$, and the rest of $Z\setminus (s\cup t)$ lies in $C_j$. Hence $Z\in [s\cup t,C_j]$ and $Z\notin N_j$. This proves $[s,B]\cap N=\varnothing$.

The final $[s,B]$ is star-open and disjoint from $N$, so it is also disjoint from the star-closure of $N$. Every basic neighborhood therefore has a nonempty open refinement missing that closure. This Ellentuck meagre-set fusion lemma provesIndeed, we obtained the stronger completely Ramsey-null property. Testing all subsets of the selected prefix was essential; testing just the entire prefix would not cover every infinite subset of $B$.

Identify the hypercube graph $Q_n$ with $\mathcal{P}([n])$, joining two sets when their symmetric difference has size one. Write $N[A]$ for the closed graph neighbourhood of $A$, and $N_t[A]$ for its radius-$t$ neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let $I_m$ be the first $m$ vertices in this order. Harper theorem isEquivalently, $I_m$ minimizes the external vertex boundary at fixed size. We will also obtain $|N_t[A]|\ge |N_t[I_{|A|}]|$ for every integer $t\ge 0$.

Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level $r$, and a lexicographic prefix $\mathcal{L}$ at level $r$. For $r\ge 1$, its closed graph neighbourhood contains every set of size at most $r$, and its only further members are the upper shadow of $\mathcal{L}$. An $(r+1)$-set lies in this upper shadow exactly when its lexicographically earliest $r$-subset lies in $\mathcal{L}$. That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For $r=0$, the closed graph neighbourhood of $\{\varnothing \}$ is the union of levels zero and one. The empty initial segment causes no exception.

Induct on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write the sections of $A$ as $A_0,A_1\subseteq Q_{n-1}$, deleting $i$ from the latter section. Replace them by the initial segments $I_a,I_b$ with $a=|A_0|$, $b=|A_1|$. The sections of the old closed graph neighbourhood areBy induction their sizes are at least $\max \{|N[I_a]|,b\}$ and $\max \{|N[I_b]|,a\}$, respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.

Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family $B$ whose sections in every coordinate are initial segments. If $B$ itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex $X$ and the latest present vertex $Y$, with $X\prec Y$. They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence $Y=X^c$. Nor can a vertex $Z$ lie between them: if $Z$ is present, pairing it with $X$ would force $Z=X^c=Y$; if absent, pairing it with $Y$ would force $Z=Y^c=X$. Thus $X,Y$ are consecutive, and $B$ is obtained from $I_{|B|}$ by replacing its last vertex $X$ with the next vertex $Y$.

There are only two possibilities for these terminal families for simplicial section compression. If $|X|<|Y|$, consecutiveness makes $X$ the last $k$-set and $Y$ the first $(k+1)$-set. Complementarity forces $n=2k+1$, $X=\{k+2,\dots ,2k+1\}$ and $Y=\{1,\dots ,k+1\}$. For $n\ge 3$, the corresponding $B$ contains all sets of size at most $k$ except $X$, and additionally $Y$. Every $(k+1)$-set has at least two $k$-subsets, so at least one belongs to $B$. The missing $X$ has a $(k-1)$-subset in $B$. Consequently $N[B]$ contains every set of size at most $k+1$, which is exactly $N[I_{|B|}]$.

If $|X|=|Y|$, then $n=2k$. Since $X,Y$ are complementary, the smaller one contains coordinate $1$. Consecutiveness forces $X$ to be the last $k$-set containing $1$, and $Y$ the first $k$-set avoiding $1$:The initial segment consists of all sets of size less than $k$ and all $k$-sets containing $1$. Its closed graph neighbourhood contains all sets of size at most $k$ and all $(k+1)$-sets containing $1$. For $k\ge 2$, each such $(k+1)$-set has $k\ge 2$ $k$-subsets containing $1$, so removing only $X$ leaves one in $B$. All sets of size at most $k$ are still in $N[B]$, because all levels below $k$ belong to $B$. Hence again $N[I_{|B|}]\subseteq N[B]$. For $k=1$, the two families are related by exchanging coordinates and both have the whole $Q_2$ as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.

For the radius-$t$ version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If $|N_{t-1}[A]|\ge |N_{t-1}[I_m]|$, applying Harper theorem to $N_{t-1}[A]$ therefore gives $|N_t[A]|\ge |N_t[I_m]|$. Induction on $t$ proves the asserted extension.

A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs $G_n$ of diameter $D_n$, use normalized graph distance $d_n=d_{G_n}/D_n$ and uniform probability measure. For every fixed $\epsilon >0$, requireFor $Q_n$ this normalization is normalized Hamming distance $d_H/n$, since its diameter is $n$.

If $|A|\ge 2^{n-1}$, the corresponding initial segment contains the Hamming ball about $\varnothing$ of radius $b_n=\lfloor (n-1)/2\rfloor$. The radius-$t$ version of Harper theorem impliesUse the precise Hoeffding inequality $\mathbb{P}(Z_n-n/2\ge u)\le \exp (-2u^2/n)$ for $u\ge 0$. One can also derive this estimate directly: the moment-generating function of $Z_n-n/2$ is $\cosh (\lambda /2{)}^n\le \exp (n{\lambda }^2/8)$; the exponential Markov inequality followed by minimization at $\lambda =4u/n$ gives the bound. With $t=\lfloor \epsilon n\rfloor$, we have $b_n+t\ge n/2+\epsilon n-2$. Thus, whenever $\epsilon n>2$,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any $a>0$, choose $c$ with $1/(4c^2)<a$. The Chebyshev inequality for $Z_n$, whose variance is $n/4$, makes the Hamming ball of radius $\lfloor n/2-c\sqrt{n}\rfloor$ have fewer than $a{2}^n$ vertices. An initial segment of size at least $a{2}^n$ contains that ball. Enlarging by $\lfloor \epsilon n\rfloor$ and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such $A$. The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.

Equality in Harper theorem does not determine a down-set up to isomorphism. In $Q_4$, takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to $A$. Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to $N[A]$. The four-element set does not. Hence $|N[A]|=1+4+6+4=15$.

The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs $12,13,14,23$. Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size $15$, proving extremality of $A$. Nevertheless the induced graphs are not isomorphic: in $A$, the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely $\varnothing$ and $\{1\}$. Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.

We prove edit-distance stability for clique-free graphs by induction on $r$, using the symmetric difference of edge sets as the distance. For $r=1$, a $K_2$-free graph is edgeless, and there is nothing to change. For $r\ge 2$, choose a vertex of maximum degree $d$, let $A$ be its neighbourhood and put $B=V(G)\setminus A$. Then $G[A]$ is $K_r$-free. WriteBoth deficits are nonnegative by the Turan theorem. Since every vertex of $B$ has degree at most $d=|A|$,The complete $r$-partite graph formed from an $(r-1)$-partite Turán graph on $A$ and the new class $B$ has at most $t_r(n)$ edges. Thus $L=t_r(n)-t_{r-1}(d)-|A||B|\ge 0$, and direct subtraction givesBy induction, edit $G[A]$ into a complete $(r-1)$-partite graph using at most $3D_A$ changes. Delete the $b$ edges inside $B$, and add the $m$ missing edges between $A$ and $B$. The resulting graph is complete $r$-partite on the same vertex set, andwhere the inequality uses $m\ge 2b$. The required edit distance is at most $3k$. Empty partition classes are allowed; a sufficiently dense nondegenerate case has the usual full complement of classes.

For the odd-cycle conclusion, use two standard consequences of the Szemerédi regularity lemma, stated explicitly. The triangle removal lemma says that for every $\alpha >0$, some $\beta >0$ ensures that a graph with at most $\beta n^3$ triangles in a graph can be made triangle-free by deleting at most $\alpha \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, for all sufficiently large $n$. Also, for each fixed odd length $\ell \ge 3$ and each $\beta >0$, there is $\zeta >0$ such that a graph with at least $\beta n^3$ triangles in a graph contains at least $\zeta n^{\ell }$ copies of $C_{\ell }$.

For clarity, the latter odd-cycle copies from positive triangle density consequence follows by applying regularity with error small relative to $\beta$, removing exceptional, irregular and very sparse pairs, and retaining a triangle in a graph among the remaining regular dense pairs. The graph embedding lemma for regular pairs counts a positive constant times $n^{\ell }$ embeddings of any fixed graph properly three-coloured into those three clusters, including $C_{\ell }$. Dividing by the fixed number of descriptions of a cycle gives the same conclusion for unlabelled copies.

Apply triangle in a graph removal with $\alpha =ϵ$, and take the resulting $\beta$. A $C_{2013}$-free graph cannot have $\beta n^3$ triangles in a graph for large $n$, by the preceding consequence. Delete at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges to obtain a triangle-free $G^{\prime }$. With $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$,Apply the proved stability result with $r=2$. The resulting complete bipartite graph $H$ satisfiesChoose $n_0(ϵ)$ also large enough that $3n/4\le 4ϵN$. Then the distance is at most $11ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

For the unheaded continuation, use the same $\beta$ and its associated $\zeta$, and set $\delta =\zeta /2$. Having at most $\delta n^{2013}$ cycles rules out $\beta n^3$ triangles in a graph just as before. The identical deletion and stability calculation applies. A sufficiently small $\delta =\delta (ϵ)>0$ gives the same $11ϵ$ bound.

Write $[M{]}^{\omega }$ for the infinite subsets of an infinite $M\subseteq \mathbb{N}$. A Ramsey set of infinite subsets $Y\subseteq [\mathbb{N}{]}^{\omega }$ has an infinite homogeneous set $M$: either $[M{]}^{\omega }\subseteq Y$ or $[M{]}^{\omega }\cap Y=\varnothing$. The proof below actually supplies homogeneous refinements within every infinite reservoir, and with any fixed initial finite stem; this stronger property is that of a completely Ramsey set.

For a non-Ramsey example, identify two infinite sets when their symmetric difference is finite, and choose one representative $R$ for each equivalence class. Define a two-colouring bywhere $R$ is the representative of $A$'s class. Removing one point changes this parity. Thus, for every infinite $M$, the two subsets $M$ and $M\setminus \{\min M\}$ have opposite colours. The zero-colour family meets every $[M{]}^{\omega }$ and so does its complement. Hence the zero-colour family is not Ramsey. This finite-symmetric-difference parity colouring uses a choice of representatives; no definability or regularity is being claimed for that first example.

To prove the open-set assertion, for a finite increasing set $s$ and an infinite tail $A$ above $\max s$ defineThe star topology, or Ellentuck topology, has these sets as basic open sets. For an empty stem there is no lower-bound restriction. More generally $[s,A]$ always uses only the points of $A$ above $\max s$. The ordinary topology on infinite subsets, denoted $\tau$, has cylinders $[s]=\{B:s\text{ is an initial segment of }B\}$ as a basis. The two topologies must not be confused.

Fix any family $Y$, initially without any openness assumption. An infinite $A$ accepts a stem $s$ if $[s,A]\subseteq Y$, and rejects it if no infinite subset of its tail accepts $s$. Every infinite reservoir has an infinite refinement deciding $s$: take an accepting refinement if one exists, and otherwise the reservoir itself rejects. Acceptance and rejection are both inherited by infinite refinements. These facts follow from the definitions, giving acceptance and rejection of finite stems.

First refine the initial reservoir to decide the empty stem. If it accepts, its infinite subsets already lie in $Y$. Otherwise start from an infinite reservoir rejecting the empty stem. Choose an increasing point $a_1$, then thin its remaining tail finitely many times to decide all subsets of $\{a_1\}$. Having chosen $a_1,\dots ,a_n$, choose $a_{n+1}$ from the current tail and refine the remaining tail to decide all subsets of $\{a_1,\dots ,a_{n+1}\}$. Each stage has only finitely many stems to handle. Let $L=\{a_1,a_2,\dots \}$.

For every finite $s\subset L$, at the stage of its largest point the reservoir was made to decide $s$, and all later chosen points remain inside that reservoir. Heredity therefore makes the tail of $L$ decide $s$. Moreover $L$ still rejects the empty stem. This proves deciding all finite stems by fusion without assuming a separate fusion theorem.

Suppose $L$ rejects a finite $s\subset L$. There are only finitely many $a\in L$ above $\max s$ for which $L$'s tail above $a$ accepts $s\cup \{a\}$. For if there were infinitely many, collect them into $C$. Every infinite $B\subset C$ has least point $a$ of this kind, and its remaining tail lies in the accepting tail of $L$. Hence $s\cup B\in Y$ for every such $B$, so $C$ would accept $s$, contradicting rejection. This proves finitely many accepting extensions of a rejected stem.

Now choose increasing $b_1,b_2,\dots$ from $L$ so that every subset of the chosen finite prefix is rejected by the appropriate tail of $L$. The empty prefix is rejected. At the next step, for each of the finitely many already chosen subsets $s$, avoid the finitely many accepting successors just identified. All other successors are rejected, since the previous fusion made every finite stem in $L$ decided. Thus one can choose the next point beyond the finite forbidden union. With $M=\{b_1,b_2,\dots \}$, every finite $s\subset M$ is rejected.

Now assume $Y$ is star-open. If some infinite $B\subset M$ lay in $Y$, there would be a basic neighbourhood $[s,A]\subseteq Y$ containing $B$. Here $s$ is a finite initial segment of $B$, and its infinite tail $C=B\setminus s$ lies in $A$ and in the relevant tail of $L$. Then $[s,C]\subseteq [s,A]\subseteq Y$, so $C$ accepts $s$, contradicting rejection. Therefore $[M{]}^{\omega }\cap Y=\varnothing$. In the earlier acceptance case, $[M{]}^{\omega }\subseteq Y$. We have provedThe construction works with any infinite starting reservoir. Keeping an initial finite stem fixed and applying the same acceptance/rejection argument to its tails proves the completely Ramsey set conclusion as well. This supplies the full fusion proof for open Ellentuck sets; no unproved course combinatorial lemma has been used.

For the final request, a family has the Baire property in the ordinary infinite-subset topology if it differs from a $\tau$-open family by a $\tau$-meagre set. We construct a non-Ramsey family which is already $\tau$-nowhere dense. LetThe gap-doubling closed family of infinite subsets $D$ is $\tau$-closed: a violation is witnessed by a finite initial segment, whose whole cylinder lies outside $D$. It is nowhere dense: inside any cylinder, extend the stem by two sufficiently large consecutive integers $k,k+1$; the resulting smaller cylinder violates the gap inequality and is disjoint from $D$.

For every infinite $M$, the set $D\cap [M{]}^{\omega }$ has cardinality $\mathfrak{c}=2^{{\aleph }_0}$. To prove the lower bound, build a binary tree of finite gap-doubling sequences using points of $M$, choosing two distinct next points above twice the previous point at every node. Distinct infinite binary branches give distinct increasing sets. The upper bound follows because all these sets are subsets of the countable set $\mathbb{N}$.

Well-order all infinite subsets as $(M_{\alpha }{)}_{\alpha <\mathfrak{c}}$, using the initial ordinal of that cardinality. At stage $\alpha$, choose two previously unused setsand reserve both permanently. There are fewer than $\mathfrak{c}$ previously reserved sets but $\mathfrak{c}$ candidates, so this recursion always continues. This argument does not assume that the continuum is a regular cardinal. Set $X=\{R_{\alpha }:\alpha <\mathfrak{c}\}$. Every cone $[M_{\alpha }{]}^{\omega }$ contains its red choice in $X$ and its blue choice outside $X$; the blue choices can never become later red choices. Therefore $X$ is not Ramsey.

But $X\subseteq D$, and $D$ is closed nowhere dense, so the closure of $X$ also has empty interior. Thus $X$ is nowhere dense, hence meagre, and $X△\varnothing =X$ proves its ordinary Baire property. We have obtained a meagre set meeting every Ramsey cone in both colours:This explains why ordinary Baire regularity cannot replace the star-topology regularity in the open-set theorem. A family supported only on the infinite subsets of a fixed sparse set would not suffice for this counterexample: another infinite set could give an entirely disjoint cone. The gap-doubling family used here instead meets every cone in continuum many candidates.

The Kruskal-Katona theorem. For a uniform set family $\mathcal{F}$ of $r$-sets, its lower shadow isIf ${\mathcal{I}}_r(a)$ consists of the first $a$ $r$-sets in colexicographic order, thenHere $B<A$ in colexicographic order means that the largest element of the symmetric difference $A△B$ belongs to $A$. In terms of the unique greedy binomial representationthe bound isFor $a=0$ the right side is zero. We prove both the minimizing assertion and this formula.

First, the lower shadow of a colexicographic initial segment is a colexicographic initial segment. One way to check this is to extend an $(r-1)$-set $D$ by its least missing positive integer; this is its earliest $r$-set extension in colexicographic order. If $E<D$, the earliest extension of $E$ is no later than the earliest extension of $D$. To see the latter assertion, let $j=\max (D△E)\in D$. If $E$ misses an integer below $j$, its least missing integer is below $j$, so its earliest extension is still earlier than the earliest extension of $D$. Otherwise $E$ contains every integer below $j$. Above $j$ the two sets agree, and their equal sizes force $D$ to contain $j$ and all but one integer below $j$. Adding that missing integer to $D$, or adding $j$ to $E$, gives the same earliest extension. Thus every set earlier than a member of the lower shadow is also in that lower shadow.

We now prove the minimizing assertion by induction on the size $N$ of a finite ground set. The case $r=1$ is immediate: a nonempty uniform set family of singletons has lower shadow $\{\varnothing \}$. The empty case and $r=N$ are also immediate. For a coordinate $i$, write the two sections of $\mathcal{F}$ asThey are respectively $r$- and $(r-1)$-uniform set families on $[N]\setminus \{i\}$. Perform a colexicographic section compression: replace each section by the colexicographic initial segment of the same size. The two sections of the lower shadow before this operation areBy the inductive hypothesis the individual lower shadows do not grow. After colexicographic section compression, both families in the displayed union are colexicographic initial segments, so their union has the larger of their two sizes. This is no greater than the original union. Consequently colexicographic section compression preserves $|\mathcal{F}|$ and does not increase $|\partial \mathcal{F}|$. A section of size zero causes no difficulty; a section of $0$-sets is already compressed and its lower shadow is empty.

Repeat any colexicographic section compression that changes the family. The sum of the positions of its members in colexicographic order strictly decreases, since restriction to either fixed-coordinate section preserves that order. Hence the process terminates at a family $\mathcal{G}$ all of whose sections are colexicographic initial segments.

There is only one possible obstruction to $\mathcal{G}$ itself being a colexicographic initial segment. Suppose $B<A$, $A\in \mathcal{G}$ and $B\notin \mathcal{G}$. No coordinate can belong to both $A,B$, or to neither: either possibility would contradict the compressed section at that coordinate. Thus $A,B$ partition $[N]$, and $N=2r$. Moreover, every such inversion must use this same complementary pair: any omitted set below $A$ equals $A^c=B$, and any included set above $B$ equals $B^c=A$. These observations also rule out an inversion completely before or after this pair. A set strictly between $B$ and $A$ would have to be both present, by comparison with $A$, and absent, by comparison with $B$. Therefore $B,A$ are consecutive in colexicographic order. Since $A$ contains $2r$ and $B$ does not, they must beThus the exceptional family is $[2r-1{]}^{(r)}\setminus \{B\}\cup \{A\}$. For $r\ge 2$, deleting $B$ leaves every $(r-1)$-set of $[2r-1]$ in the lower shadow: each has $r$ extensions inside $[2r-1]$, so at least one remains. Its lower shadow therefore contains the lower shadow of the equally sized colexicographic initial segment $[2r-1{]}^{(r)}$. The case $r=1$ was already handled. This proves the minimizing assertion in all cases.

Finally the greedy binomial representation describes the successive blocks of a colexicographic initial segment. Its first block is $[k_r{]}^{(r)}$, and the remaining sets are obtained by adding $k_r+1$ to an initial segment of $(r-1)$-sets inside $[k_r]$. The lower shadow without $k_r+1$ has $\left(\genfrac{}{}{0ex}{}{k_r}{r-1}\right)$ members; the lower shadow containing $k_r+1$ is the corresponding lower-rank lower shadow. Repeating this decomposition proves the displayed binomial coefficient formula and completes the Kruskal-Katona theorem proof.

The specified initial segment covers every $r$-set of $[m]$. Assume $m\ge r+1$ and $r\ge 1$, the nontrivial range. The last $r$-set of $[m]$ in colexicographic order isIts earliest $(r+1)$-set extension is $\{1\}\cup R$. Exactly $m-r-1$ sets of $[m{]}^{(r+1)}$ come after this extension: they are $\{x\}\cup R$ with $2\le x\le m-r$. Its position is thereforeAt the stated threshold, $R$ belongs to $\partial \mathcal{I}$. Since the lower shadow is a colexicographic initial segment,For $r=0$, the threshold is $1$ and a nonempty family of singletons has $\varnothing$ in its lower shadow. If $m=r\ge 1$, the threshold is again $1$; the first $(r+1)$-set is $[r+1]$, which contains $[r{]}^{(r)}$. If $m<r$, the desired inclusion is empty and automatic.

The nonuniform bound. Suppose first that $1\le r\le m$ and, contrapositively, that $|\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$. Let $\mathcal{J}$ be the colexicographic initial segment of $r$-sets of size $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$; this consists of $[m{]}^{(r)}$ with its last member $R$ removed. For each $j\ge r$, put ${\mathcal{A}}_j=\mathcal{A}\cap [n{]}^{(j)}$, and replace it by the equally sized colexicographic initial segment ${\mathcal{I}}_j$.

Iterating the Kruskal-Katona theorem shows that the iterated lower shadow down to size $r$ of ${\mathcal{I}}_j$ has no more members than the corresponding iterated lower shadow of ${\mathcal{A}}_j$. Indeed, at each step initial segments minimize the next lower shadow, and its minimum size is increasing in the input size. The latter iterated lower shadow lies in $\mathcal{B}$. Therefore every $r$-subset of every member of ${\mathcal{I}}_j$ lies in $\mathcal{J}$.

For $j\ge r$, a $j$-set with this property must lie inside $[m]$: otherwise an $r$-subset containing an element larger than $m$ would lie outside $\mathcal{J}$. Among $j$-sets inside $[m]$, exactly those containing $R$ are forbidden. HenceAdding these bounds proves the contrapositive. Thus the strict threshold forcesWhen $r=0$, the threshold merely says that $\mathcal{A}$ is nonempty, so $\mathcal{B}=\{\varnothing \}$. When $m<r$, the claimed lower bound is zero. The strict inequality is sharp: the family of all subsets of $[m]$ of size at least $r$ that do not contain $R$ attains the displayed sum and has exactly $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$ members in its size-$r$ iterated lower shadow.

On $[\kappa {]}^{\omega }$, declare $A\sim B$ when their symmetric difference is finite. Use the well-ordering theorem to choose one representative $R_{[A]}$ from each equivalence class, and color byRemoving one point from a countably infinite set does not change its equivalence class and reverses this parity. For any $H\subseteq \kappa$ of order type $\omega$ and $x\in H$, both $H$ and $H\setminus \{x\}$ belong to $[H{]}^{\omega }$ and receive different colors. There is no homogeneous $H$ of order type $\omega$. This proves the negative infinite-arity partition relationThe slashed arrow in the PDF is essential.

The first condition concerns the domains: their symmetric difference $A△B$ must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because $A△A=\varnothing$, and a symmetric relation because $A△B=B△A$. For the transitive relation property, membership can differ between $A$ and $C$ only if it differs between $A$ and $B$ or between $B$ and $C$. ThusA set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.

For a finite generating set $S$, the Følner condition requires that for every $\epsilon >0$ there be a nonempty finite $F\subseteq G$ such thatwhere $△$ denotes symmetric difference. Choose a Følner sequence $(F_n)$ and define normalized counting functions on all subsets $A\subseteq G$ byBy compactness of the product $[0,1{]}^{\mathcal{P}(G)}$, some subnet converges pointwise to a function $m$. The identities ${\mu }_n(G)=1$ and finite additivity on disjoint subsets pass to the limit, so $m$ is a finitely additive probability measure.

For a fixed $g=s_1\cdots s_{\ell }$, the triangle inequality for symmetric differences givesConsequentlyso $m(gA)=m(A)$. The limit is left invariant and the Følner condition implies amenability. Thus every finitely generated group satisfying the Følner condition is amenable.

Requiring exactly one condition means taking the symmetric difference of the two sets. Subtract their shared cases twice from the two individual counts:Equivalently, remove the twenty-four arrangements satisfying both conditions from the inclusive count $216$.