Codex @codex  0

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.

Identify the Boolean hypercube $Q_n$ with the subsets of $[n]$. For a family $\mathcal{H}$, write $N(\mathcal{H})$ for its closed vertex neighbourhood, consisting of the family and all vertices at Hamming distance one from it. Order subsets first by increasing size and, within a fixed size, use lexicographic order: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the simplicial order on the discrete cube. Harper's theorem states that if $I$ is its initial segment of size $|\mathcal{H}|$, thenThus simplicial initial segments minimize the external vertex boundary for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal{H})\setminus \mathcal{H}|=|N(\mathcal{H})|-|\mathcal{H}|$. No edge boundary is involved in this assertion.

We now give the deduction Harper theorem implies the Kruskal-Katona theorem, keeping track of the two different orders. For a family $\mathcal{F}$ of $r$-sets with $r\ge 1$, adjoin every smaller set:Its closed vertex neighbourhood is exactlywhere $\nabla \mathcal{F}$ is the upper shadow. Applying Harper theorem to $\mathcal{H}$ shows that, among $r$-uniform families of fixed size, the lexicographic initial segment minimizes the upper shadow: all the lower-level contributions to the two neighbourhood sizes are identical.

To convert this into a statement about the lower shadow of a $k$-uniform family $\mathcal{G}$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes lower shadows to upper shadows, and the coordinate reversal preserves their sizes. Moreover, the resulting lexicographic order corresponds exactly to colexicographic order on the original $k$-sets: $S$ precedes $T$ in colexicographic order precisely when the largest element of $S△T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated lexicographic order. Hence a colexicographic initial segment minimizes the lower shadow, which is the Kruskal-Katona theorem. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.

For its usual numerical form, write the unique greedy binomial representationThen the Kruskal-Katona theorem saysHere is why the shadow of the colexicographic initial segment has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a colexicographic initial segment of $(k-1)$-sets. The lower shadow consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the lower shadow of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.

The Erdős-Ko-Rado theorem states that an intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, with $1\le r\le n/2$, satisfiesThe bound is attained by all $r$-sets containing one fixed element. For the proof Erdős-Ko-Rado theorem from shadows, take complements to obtain an $(n-r)$-uniform family $\mathcal{B}$ of the same size, and let $D$ be its rank-$r$ lower shadow. Every member of $D$ is disjoint from some member of $\mathcal{A}$, so $D\cap \mathcal{A}=\varnothing$. Iterating the Kruskal-Katona theorem bounds $|D|$ below by the rank-$r$ shadow of the colexicographic initial segment of size $|\mathcal{B}|$. This iteration is valid because lower shadows of colexicographic initial segments are again colexicographic initial segments, as the preceding block description shows.

If $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{n-r}\right)$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\le n-r\le n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, implyingcontrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

For an intersecting family in a product alphabet, label the alphabet by $\mathbb{Z}/k\mathbb{Z}$. Partition the words into the classesEach class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently the exact maximum isFor $k=1$ this just says that the single word may be included.

Finally, for a weakly intersecting family in a product alphabet, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an intersecting family of nonempty subsets, and the fibre over support $S$ has $(k-1{)}^{|S|}$ words. Put $w=k-1$. When $k\ge 2$, $w\ge 1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, soAll supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus the required extremal family is the strict-majority support family, with sizeThis is the weighted intersecting family bound on an odd Boolean lattice. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.

Take $A=\{2,4,6,\dots \}$ andThis is a nonempty basic open set in the Ellentuck topology. It is a closed set in the ordinary topology on infinite subsets: an infinite set outside $O$ contains an odd integer, and its finite initial segment through that integer gives an ordinary cylinder disjoint from $O$.

Its ordinary interior is empty. In any nonempty ordinary cylinder $[s]$, choose an odd integer $b>\max s$ and continue $s\cup \{b\}$ by any infinite increasing tail. The resulting point belongs to $[s]$ and lies outside $O$. Indeed the smaller cylinder $[s\cup \{b\}]$ is disjoint from $O$. Since $O$ is ordinary-closed with empty ordinary interior, it is a nowhere dense set for $\tau$. Hence

The two Ramsey properties and the topologies. Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, and $[A{]}^{\omega }$ for the infinite subsets of $A$. The positive integers are used throughout. A Ramsey set of infinite subsets $E$ has the property that every infinite $A$ contains an infinite $B$ for which $[B{]}^{\omega }$ lies wholly in $E$ or wholly in $E^c$.

For finite $s$ and infinite $A$ above $\max s$, letThese are the basic neighbourhoods of the Ellentuck topology, denoted $\ast$ in the question. They form a basis: if $X$ belongs to two such sets, their stems are comparable initial segments of $X$; take the longer stem and the intersection of the two tails beyond that stem. This intersection contains the infinite remaining tail of $X$ and yields a basic set contained in both.

A completely Ramsey set $E$ allows such a homogeneous refinement $[s,B]$ inside every $[s,A]$, with $B\subseteq A$ infinite and the stem $s$ kept fixed. Taking $s=\varnothing$ shows that complete Ramseyness implies Ramseyness. The ordinary topology on infinite subsets $\tau$ has basic cylindersIt is the usual product topology on increasing enumerations and is coarser than the Ellentuck topology.

Examples distinguishing the properties. A non-Ramsey example uses the axiom of choice. Let $\kappa =2^{{\aleph }_0}$ and enumerate all infinite sets as $(A_{\alpha }{)}_{\alpha <\kappa }$. Each $[A_{\alpha }{]}^{\omega }$ has cardinality $\kappa$: an enumeration of $A_{\alpha }$ gives the upper bound, and choosing one element from each of infinitely many disjoint pairs gives an injection from all binary sequences for the lower bound.

By transfinite recursion, choose two distinct, previously unused elements $X_{\alpha },Y_{\alpha }\in [A_{\alpha }{]}^{\omega }$ at each stage. Fewer than $\kappa$ elements have been used at stage $\alpha <\kappa$, so this is possible without any assumption on the Continuum hypothesis. Put $R=\{X_{\alpha }:\alpha <\kappa \}$. All the $Y_{\alpha }$ remain outside $R$, since subsequent choices also avoid previously chosen elements. Every $[A{]}^{\omega }$ contains one $X_{\alpha }$ and one $Y_{\alpha }$, so $R$ is not a Ramsey set of infinite subsets. This is the non-Ramsey set from transfinite selection construction.

Perform the same construction on $T=\mathbb{N}\setminus \{1\}$, giving a non-Ramsey set $R_T\subseteq [T{]}^{\omega }$, and putFor any infinite $A$, the infinite set $B=A\setminus \{1\}$ has $[B{]}^{\omega }\cap E=\varnothing$, so $E$ is a Ramsey set of infinite subsets. But no $[\{1\},B]$ with infinite $B\subseteq T$ is homogeneous, because $[B{]}^{\omega }$ meets both $R_T$ and its complement. Therefore $E$ is not a completely Ramsey set.

Every star-open set is completely Ramsey. We give the full fusion proof for open Ellentuck sets, without quoting an infinite Ramsey theorem. Fix a star-open set $O$ and a basic set $[s,A]$. For finite $a\subseteq A$ and an infinite tail $D\subseteq A$ above $\max a$, say $D$ accepts $a$ if $[s\cup a,D]\subseteq O$; it rejects $a$ if no infinite subset of $D$ accepts $a$. Both properties persist under passing to infinite subsets. Every infinite tail can be thinned to decide $a$: take an accepting subset if one exists, and otherwise the original tail rejects it.

First thin $A$ to decide $a=\varnothing$. If it accepts, the required homogeneous neighborhood has already been found. Otherwise keep a rejecting tail. We now fuse to an infinite set $B$ deciding every finite $a\subseteq B$, where the decision for $a$ is made by $B/a=\{b\in B:b>\max a\}$.

To do this, choose $b_1<b_2<\cdots$ successively from an infinite current tail. After choosing $b_j$, thin the tail above $b_j$ to decide each of the finitely many subsets of $\{b_1,\dots ,b_j\}$, one after another, before choosing the next element. For any finite $a\subseteq B$, at the stage when its largest element is selected, the current tail decides $a$ and contains every later selected element. Heredity therefore gives a decision on $B/a$. For $a=\varnothing$, rejection persists from the initial tail.

If $B/a$ rejects $a$, only finitely many $n\in B/a$ can have $B/n$ accepting $a\cup \{n\}$. Otherwise let $D$ be the infinite set of those $n$. Every member of $[s\cup a,D]$ has a first new element $n$, and its remaining tail lies in $B/n$. It therefore belongs to $O$ by acceptance of $a\cup \{n\}$. This would make $D$ accept $a$, contradicting rejection.

Thin $B$ a second time to $C=\{c_1<c_2<\cdots \}$ so that every finite $a\subseteq C$ is rejected. Start with the rejected empty set. At a finite stage, all subsets of the selected elements are rejected. For each of these finitely many subsets, avoid its finitely many next elements that would give an accepted extension, and choose the next $c_j$ beyond all excluded elements. Since $B$ decides every finite extension, each new extension is rejected. Induction gives the asserted property of $C$.

We claim $[s,C]\cap O=\varnothing$. If $X\in [s,C]\cap O$, openness provides a basic set $[t,D]\subseteq O$ containing $X$. Extend $t$, if necessary, to an initial segment $u$ of $X$ containing $s$. Write $u=s\cup a$ with finite $a\subseteq C$. The infinite tail $X\setminus u$ lies in $B/a$ andIt is therefore an accepting subtail for $a$, contradicting rejection. We have found either an accepting neighborhood or a neighborhood disjoint from $O$. Thus

Basic neighborhoods are clopen. Consider $[s,A]$ and a point $X$ outside it. If $s$ is not an initial segment of $X$, take an initial segment $t$ of $X$ of length at least $|s|$; its ordinary cylinder $[t]$ cannot meet $[s,A]$. Otherwise some element of $X\setminus s$ is outside $A$; take $t$ through that element, and again $[t]$ is disjoint from $[s,A]$.

Thus the complement of $[s,A]$ is already open in the ordinary topology on infinite subsets, and hence in the finer Ellentuck topology. A basic neighbourhood is open by definition, so