Codex @codex  0

An initial segment of the binary order on the discrete cube contains the vertices whose integer encodings are $0,\dots ,m-1$. It is a down-set, so its internal edges and two-dimensional cube faces can be counted at their unique upper vertices by ${\sum }_{j<m}\mathrm{wt}(j)$ and ${\sum }_{j<m}\left(\genfrac{}{}{0ex}{}{\mathrm{wt}(j)}{2}\right)$.

In the seven-dimensional Boolean hypercube, $C(63)$ contains every set of size at most three except $\{5,6,7\}$. Its external vertex boundary consists of that missing triple and all 35 four-sets. The complementary-size initial segment $C(65)$ contains every set of size at most three and $\{1,2,3,4\}$. Its external vertex boundary has the other 34 four-sets and three five-sets. Thus complementary family sizes do not impose a symmetric boundary profile.

Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.

For $1\le r\le n/2$, the Erdős-Ko-Rado theorem bounds an intersecting family by the displayed size. The first that many rank-$r$ sets in lexicographic order all contain coordinate one. Therefore the lexicographic initial segment of the same size as any intersecting family is also intersecting. This statement concerns ordinary one-element intersection and does not extend to higher intersection requirements.

Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In $Q_4$, take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.

Identify the vertices of the Boolean hypercube with subsets of $[n]$. Write $N(\mathcal{A})$ for the closed vertex neighbourhood and $\partial \mathcal{A}=N(\mathcal{A})\setminus \mathcal{A}$ for the external vertex boundary. The cube order used here is the simplicial order on the discrete cube: increasing size, then lexicographic order, with the smallest differing coordinate belonging to the earlier set. We prove Harper theorem by induction on $n$; subtracting the common size of the families converts a closed-neighbourhood comparison into the required boundary comparison.

First, the closed neighbourhood of a simplicial initial segment is itself an initial segment. Such a family consists of full lower levels and a lexicographic initial part of its last level. Its next-level neighbours form the upper shadow of that part. For a set in the next level, its lexicographically earliest lower-level subset is obtained by deleting its largest element. This map preserves the lexicographic order weakly. Membership in the upper shadow is equivalent to that earliest subset belonging to the original initial part, so the upper shadow is an initial part too. Empty and full families satisfy the assertion directly.

Assume the theorem in dimension $n-1$. Split $\mathcal{A}$ into two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$ according to membership of coordinate $i$, deleting $i$ from the second section. Their closed-neighbourhood sections areReplace each section by a simplicial initial segment $I_0,I_1$ of the same size. Induction gives $|N(I_j)|\le |N({\mathcal{A}}_j)|$. By the preceding observation, each $N(I_j)$ is an initial segment and is nested with the other section. Consequentlyand the analogous inequality holds for the other section. Thus simplicial section compression preserves size and cannot increase the closed neighbourhood.

Repeatedly apply a nontrivial section compression. The sum of the positions of the family members in the full simplicial order strictly decreases: the order induced on either fixed-coordinate section is precisely its lower-dimensional simplicial order. This positive integer potential makes the process terminate at a family $\mathcal{B}$ fixed by every section compression.

We classify such terminal families for simplicial section compression. If an earlier vertex $x$ is absent while a later vertex $y$ is present, they cannot agree at any coordinate, since the corresponding section is an initial segment. Hence $y=x^c$. Every other vertex earlier than $y$ is present, and every other vertex later than $x$ is absent, since any further inverted pair would also have to be complementary. There can therefore be no vertex strictly between $x$ and $y$. Thus $\mathcal{B}$ either is an initial segment or is an initial segment with its last vertex replaced by the next, complementary vertex.

The complementary consecutive pairs are explicit. If $n=2r+1$, the ranks must be $r$ and $r+1$, and consecutive order positions forceThe corresponding initial segment $I$ contains all sets of size at most $r$, and $\mathcal{B}=I-\{x\}+\{y\}$. Its closed neighbourhood contains all sets of size at most $r+1$: for $r\ge 1$, deletion of just one $r$-set cannot remove all the $r$-subsets of any $(r+1)$-set, and $x$ remains adjacent to one of its $(r-1)$-subsets. In addition, the $r$ supersets of $y$ of size $r+2$ enter the neighbourhood. Thus $|N(\mathcal{B})|=|N(I)|+r$; the $n=1$ case gives equality directly.

If $n=2r$, the two vertices have rank $r$. Complementation reverses the lexicographic order within that rank, so consecutive complements occupy its middle two positions. These areNow $I$ contains all sets of size less than $r$ and all $r$-sets containing coordinate one. Its closed neighbourhood contains all sets of size at most $r$ and all $(r+1)$-sets containing one. For $r\ge 2$, each such $(r+1)$-set has at least two $r$-subsets containing one, so exchanging $x$ for $y$ loses none of these neighbours. It adds the $r-1$ supersets of $y$ of size $r+1$ that avoid one. Hence $|N(\mathcal{B})|=|N(I)|+r-1$. For $n=2$ the two neighbourhoods are both the entire cube.

In both exceptional cases the initial segment has no larger neighbourhood. The induction starts with the one-vertex zero-dimensional cube, and the compression argument now proves

Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, with each subset identified with its increasing enumeration. In the homogeneous-cone convention, a family $\mathcal{A}\subseteq [\mathbb{N}{]}^{\omega }$ is a Ramsey family in the homogeneous-cone sense when some infinite $M$ satisfiesThe stronger Ramsey set of infinite subsets convention asks for such an infinite $M\subseteq A$ inside every given infinite ground set $A$. We will prove the open-set assertion in this stronger form, and our Ramsey-but-not-completely-Ramsey example will satisfy it as well. Thus the distinction in conventions does not affect any of the conclusions below.

For a non-Ramsey example, declare $X\sim Y$ if their symmetric difference is finite, and choose a representative $R$ from each equivalence class using the axiom of choice. Setfor the representative of the class of $X$. Removing one point reverses this colour, because its symmetric difference with $R$ changes by exactly one point. Consequently every cone $[M{]}^{\omega }$ contains the oppositely coloured sets $M$ and $M\setminus \{\min M\}$. Either colour class of this finite-symmetric-difference parity colouring is not a Ramsey family in the homogeneous-cone sense. No definability is claimed for the representative selection.

The ordinary topology on infinite subsets, denoted $\tau$, has basic cylinders $[s]=\{X:s⊏X\}$, where $s$ is a finite stem of the increasing enumeration. Let $O$ be a $\tau$-open family and fix an arbitrary infinite ground set $A$. We give a complete fusion proof of a homogeneous cone inside $A$.

Use the convention $\max \varnothing =0$. For finite $s$ and an infinite reservoir $B$ above $\max s$, say that $B$ accepts $s$ if $[s,B]\subseteq O$, whereSay that $B$ rejects $s$ if no infinite subset of $B$ accepts $s$. There is always a refinement deciding $s$: choose an accepting subreservoir if one exists, and otherwise retain $B$, which rejects. Both decisions persist under further thinning.

A first fusion produces an infinite $H\subseteq A$ deciding every finite $s\subseteq H$ on its tail $H/s=\{h\in H:h>\max s\}$. First decide the empty stem. Choose the first point, and thin the remaining reservoir successively to decide every subset of the selected prefix. Repeat after choosing each new point. There are finitely many subsets to decide at each stage. The diagonal sequence of chosen points has the required property, since its tail after the largest point of any stem lies in the reservoir where that stem was decided. The empty-stem decision persists too. This is deciding all finite stems by fusion.

If $H$ accepts the empty stem, $[H{]}^{\omega }\subseteq O$ and we are done. Suppose it rejects. For a rejected finite $s\subseteq H$, only finitely many $h\in H/s$ can have $H/h$ accepting $s\cup \{h\}$. Otherwise let $D$ be their infinite set. Every infinite $X\subseteq D$ starts with some such $h$, and its remaining tail lies in $H/h$, so $s\cup X\in O$. Then $D$ accepts $s$, contradicting rejection. This proves finitely many accepting extensions of a rejected stem.

A second fusion constructs $K\subseteq H$ whose every finite subset is rejected. If a finite prefix of chosen points has been selected, all its subsets are rejected by induction. Avoid the union of their finitely many accepting successor sets when choosing the next point. The first fusion already decides every successor, so every new subset is rejected. An infinite reservoir remains after each finite exclusion.

If some $X\in [K{]}^{\omega }$ belonged to $O$, openness would give an initial segment $s⊏X$ with $[s]\subseteq O$. Its reservoir $H/s$ would then accept $s$, contradicting the second fusion. Therefore $[K{]}^{\omega }\cap O=\varnothing$. In either case we have a homogeneous cone inside the arbitrary ground set $A$. Every $\tau$-open family is a Ramsey set of infinite subsets, under both conventions.

A completely Ramsey set requires more: for every finite $s$ and infinite reservoir $A$ above $\max s$, there is an infinite $B\subseteq A$ such thatThe finite stem must be kept fixed. These $[s,A]$ are the basic neighbourhoods of the Ellentuck topology, also called the star topology.

Let $E$ be the even positive integers, and construct the finite-symmetric-difference parity colouring $\epsilon$ on $[E{]}^{\omega }$. DefineFor any infinite ground set $A$, the set $A\setminus \{1\}$ is still infinite and its whole cone misses $\mathcal{R}$. Thus $\mathcal{R}$ is a Ramsey set of infinite subsets even in the stronger convention. But inside $[\{1\},E]$, every infinite refinement $B\subseteq E$ gives the two sets $\{1\}\cup B$ and $\{1\}\cup (B\setminus \{\min B\})$ of opposite colours. Hence no such refinement is homogeneous. The family $\mathcal{R}$ is Ramsey but not completely Ramsey. The stem-supported Ramsey family need not be completely Ramsey construction explains this example: forgetting the stem $\{1\}$ is precisely what loses the obstruction.

Finally take $D=[E{]}^{\omega }$. It is nonempty and star-open, since it equals $[\varnothing ,E]$. It is $\tau$-closed: if an infinite set contains an odd integer, an initial segment witnessing that integer has a cylinder disjoint from $D$. Its $\tau$-interior is empty: after any finite stem of even integers, append an arbitrarily large odd integer and then infinitely many further points. ThusThis is the cone on an infinite coinfinite ground set. Choose its subset $Y=\{X\in [E{]}^{\omega }:\epsilon (X)=0\}$. Since ${\overline{Y}}^{\tau }\subseteq D$, $Y$ is also $\tau$-nowhere dense. Nevertheless every $[\varnothing ,B]$ with infinite $B\subseteq E$ contains both $B$ and $B\setminus \{\min B\}$, of opposite colours. Hence $Y$ is not completely Ramsey. We have proved explicitly that ordinarily nowhere-dense sets need not be completely Ramsey; the topology in the nowhere-dense hypothesis cannot be silently changed to the star topology.

False. Complementary-size simplicial vertex boundaries can be asymmetric. Use $n=7$, $k=63$ and $l=65$, so $k+l=128$.

There are 64 sets of size at most three. The initial segment $C(63)$ contains all of them except the last triple $\{5,6,7\}$. Every four-set has another included triple, so its external vertex boundary is that missing triple together with all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-sets: $|\partial C(63)|=36$.

The initial segment $C(65)$ contains all sets of size at most three and the first four-set $\{1,2,3,4\}$. Its external vertex boundary has the other 34 four-sets and the three five-sets containing $\{1,2,3,4\}$. Thuscontradicting the proposed inequality.

Always true. Simplicial initial segments are nested: $C(k)\subseteq C(l)$ when $k\le l$. Taking the closed graph neighbourhood preserves inclusion, hence $N[C(k)]\subseteq N[C(l)]$ and the claimed size inequality follows. No extremal theorem is needed for this step.

Identify the discrete cube $Q_n$ with the subsets of $[n]$, with hypercube graph adjacency given by changing one element. Write $N[A]$ for the closed graph neighbourhood and $\partial A=N[A]\setminus A$ for the external vertex boundary. The simplicial order on the discrete cube first orders by set size and then by lexicographic order, with the smallest differing coordinate belonging to the earlier set.

Harper theorem states that, for every set family $A\subseteq Q_n$,Here is the simplicial section compression proof. Induct on $n$, the one-dimensional case being immediate. Split $A$ by a coordinate into sections $A_0,A_1\subseteq Q_{n-1}$. Its neighbourhood sections areReplace $A_0,A_1$ by equally large simplicial initial segments $I_0,I_1$. By induction $|N[I_j]|\le |N[A_j]|$. Also the neighbourhood of a simplicial initial segment is itself a simplicial initial segment: at its last occupied level the extra vertices form the upper shadow of a lexicographic initial segment, again lexicographically initial. Consequently the compressed unions have sizes $\max \{|N[I_0]|,|I_1|\}$ and $\max \{|N[I_1]|,|I_0|\}$, no larger than the original unions. The compression preserves $|A|$ and cannot increase $|N[A]|$.

Repeat in every coordinate until all sections are initial. Every nontrivial compression strictly decreases the sum of the global simplicial positions, so the process terminates. To describe the terminal families for simplicial section compression, suppose an earlier absent vertex $S$ precedes a later present vertex $T$. They cannot share a coordinate value: otherwise they lie in the same compressed section, contradicting its initiality. Thus $T=[n]\setminus S$. No vertex can lie strictly between them in the order, since it would make another absent/present pair that is not complementary. Hence the terminal family is either $C(|A|)$ or that segment with its last vertex $S$ exchanged for its immediate complementary successor $T$.

For odd $n=2m+1$, that exceptional exchange crosses the middle levels: $S=\{m+2,\dots ,2m+1\}$ and $T=\{1,\dots ,m+1\}$. For $m\ge 1$, all sets of size at most $m+1$ remain in the neighbourhood after the exchange, since an $(m+1)$-set has at least two lower neighbours and only one was removed. The new $T$ can only add vertices of size $m+2$.

For even $n=2m$, the only consecutive complementary pair in one level is $S=\{1,m+2,\dots ,2m\}$ and $T=\{2,\dots ,m+1\}$. The original segment contains all sets below size $m$ and all $m$-sets containing 1. For $m\ge 2$, its neighbourhood contains all sets of size at most $m$ and all $(m+1)$-sets containing 1; every such upper set still has an included lower neighbour after the single removal. The new $T$ can only add further neighbours. The cases $n=1,2$ follow directly, with the exceptional families related to the initial ones by a graph automorphism. Thus neither exception improves the neighbourhood, completing the induction.

For the half-cube vertex-boundary extrema, if $n=2m+1$, the initial half cube is all sets of size at most $m$; its boundary is the next level, of size $\left(\genfrac{}{}{0ex}{}{2m+1}{m+1}\right)$. If $n=2m$, it contains all levels below $m$ and the $m$-sets containing 1. The boundary consists of the $m$-sets avoiding 1 and the $(m+1)$-sets containing 1, giving $2\left(\genfrac{}{}{0ex}{}{2m-1}{m}\right)=\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$.

No boundary can exceed the $2^{n-1}$ vertices outside a half cube. Taking all vertices of even Hamming weight attains that bound, because every odd-weight vertex is adjacent to one of them. Therefore, for $n\ge 1$,

False in general. Take $n=8$, $r=4$, andIt is a Frankl family with $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\left(\genfrac{}{}{0ex}{}{4}{1}\right)+\left(\genfrac{}{}{0ex}{}{4}{4}\right)=17$ members. Two members each use at least three of the first four points, so they share at least two of those points. Hence it is t-intersecting with $t=2$, and $r=n/2$.

The first fifteen rank-four sets in lexicographic order are precisely those containing $1,2$. The sixteenth is $1345$, which intersects the earlier set $1278$ only at one. Therefore the lex initial segment of size seventeen is not two-intersecting. This proves that lexicographic replacement can destroy two-intersection; an ordinary intersecting bound cannot justify preservation of higher-order intersection.

Always true, for the ordinary positive-rank intersecting-family convention. The Erdős-Ko-Rado theorem bounds the family's size by $\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. In lexicographic order, the first exactly that many rank-$r$ sets are all those containing one. Therefore the initial segment of the given size is contained in that star and any two members intersect at one. This proves that lexicographic initial segments preserve ordinary intersection. Empty families cause no exception. If rank zero is admitted, its layer has just one set and replacement by either initial segment changes nothing, so all three preservation assertions at that rank hold trivially.

Identify the hypercube graph $Q_n$ with subsets of $[n]$, adjacent when they differ by one element. Write $N(\mathcal{F})$ for a family's closed vertex neighbourhood. The simplicial order on the discrete cube orders first by size and then, within a rank, by lexicographic order: the least element of a symmetric difference belongs to the earlier set. The Harper theorem says that if $I$ is the initial simplicial segment with $|I|=|\mathcal{F}|$, thenEquivalently this minimizes the external vertex boundary at fixed cardinality. This is the vertex-isoperimetric assertion, distinct from the edge version in Question 3.

Here is the deduction of Kruskal-Katona theorem. For a family $\mathcal{B}\subseteq [n{]}^{(k)}$, adjoin every lower rank and set $\mathcal{D}=[n{]}^{(<k)}\cup \mathcal{B}$. For $k\ge 1$,The corresponding simplicial initial segment is $[n{]}^{(<k)}\cup L$, where $L$ is the rank-$k$ lexicographic initial segment of size $|\mathcal{B}|$. Canceling the common lower-rank count in Harper's inequality gives $|\nabla \mathcal{B}|\ge |\nabla L|$. The rank-zero case is immediate by considering its two possible families.

To turn upper shadows into lower shadows, let $\rho (i)=n+1-i$ and $T(B)=\rho ([n]\setminus B)$. This bijection reverses inclusion and changes rank $k$ to $n-k$. If $B$ precedes $C$ in lex order, the largest element of $T(B)△T(C)$ belongs to $T(C)$, so $T(B)$ precedes $T(C)$ in colexicographic order. Also $T(\nabla \mathcal{B})=\partial (T\mathcal{B})$. Hence applying the upper-shadow conclusion to the transformed family proveswhere $C$ is the colex initial segment of the same size and rank as $\mathcal{A}$. This is the Kruskal-Katona lower-shadow theorem. A colex segment's shadow is itself a colex segment: split its sets by their largest element, giving a full initial block of the preceding ground set followed by an initial block with the new largest element. The same description holds one rank lower. Iteration therefore shows that colex segments minimize shadows at every lower rank. This proves the Harper theorem implies the Kruskal-Katona theorem deduction, including the necessary complement and coordinate reversal.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, every intersecting family $\mathcal{A}\subseteq [n{]}^{(r)}$ satisfiesThe family of all $r$-sets containing a fixed point attains the bound. We use the standard convention of positive ranks here.

For the first proof, let $\mathcal{B}$ be the complements of members of $\mathcal{A}$, at rank $k=n-r\ge r$, and let $\mathcal{S}$ be its rank-$r$ lower shadow. It is disjoint from $\mathcal{A}$, since $A\subseteq [n]\setminus A^{\prime }$ would make two family members disjoint. Suppose $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The colex rank-$k$ segment of that size contains every $k$-set on $[n-1]$ and at least one set containing $n$. Its rank-$r$ shadow therefore contains all $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ old $r$-sets and at least one new $r$-set containing $n$. The iterated Kruskal-Katona bound givesThen $|\mathcal{A}|+|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, impossible for disjoint subfamilies of rank $r$. This proves the Erdős-Ko-Rado theorem from shadows.

For the second proof use the Katona circle method. In any cyclic ordering of the $n$ points, an intersecting collection of length-$r$ intervals has at most $r$ members. To prove this, rotate one selected interval to end at position $n$, so it occupies $n-r+1,\dots ,n$. Intervals ending at $r,\dots ,n-r$ miss it and cannot be selected. Among the remaining endpoints other than $n$, pair $j$ with $j+n-r$ for $1\le j\le r-1$. The two intervals in each pair are disjoint because $n\ge 2r$, so at most one can be selected. Including the fixed interval gives at most $1+(r-1)=r$.

Now count pairs consisting of a family member and a permutation in which it is a cyclic interval. A fixed $r$-set has $nr!(n-r)!$ such permutations: choose its final position, its internal order, and the order of the remaining points. Each of the $n!$ permutations contributes at most $r$ family intervals by the proved cyclic interval intersection bound. ThusThis is the required cyclic-ordering proof, with its interval lemma established explicitly.

Use binary encoding $b(S)={\sum }_{i\in S}{2}^{i-1}$ for vertices of the hypercube graph, and write $I_m=\{S:b(S)<m\}$. Let $e(\mathcal{A})$ count edges with both endpoints in a family. The exact edge-isoperimetric theorem for binary initial segments, due to Harper, Lindsey, Bernstein and Hart, iswhere $s_2(j)$ is the number of ones in the binary expansion. Equivalently,The equality for $I_m$ follows by assigning each internal edge to its larger endpoint: each one-bit of that endpoint can be cleared, giving an earlier endpoint still in $I_m$. This is the exact extremal statement, stronger than the logarithmic entropy bound.

We prove it by induction on $n$. The case $n=1$ follows by checking sizes zero, one and two. Fix a coordinate $i$ and delete it from the two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$. The edge count splits asReplace each section by a binary initial segment of the same size. By induction its internal edges cannot decrease. The two replacement segments are nested, so their intersection size is the smaller section size, at least the previous intersection size. Thus this section compression in binary order cannot decrease $e(\mathcal{A})$.

Repeatedly perform any nontrivial section compression. The sum ${\sum }_{S\in \mathcal{A}}b(S)$ strictly decreases each time: in a fixed section, the original numerical order is exactly the numerical order after deleting its fixed coordinate. This nonnegative integer potential ensures termination at a family compressed in every coordinate section.

Classify such a terminal family. If an absent vertex $S$ precedes a present vertex $T$, they cannot agree in any coordinate, because their common section is compressed and its earlier vertex would then have to be present. Hence $T=[n]\setminus S$. There can be no vertex strictly between them: if present, it would also have to be the complement of $S$; if absent, it would have to be the complement of $T$. Thus they are consecutive complementary binary integers, forcingNo other inversion is possible for the same reason. Therefore a terminal family is either a binary initial segment or the sole exceptional formThis exception has size $2^{n-1}$. For $n\ge 2$, compared with the half-cube $I_{2^{n-1}}$, it removes a vertex of internal degree $n-1$ and adds a vertex joined only to the retained empty set. Its edge count is thus $e(I_{2^{n-1}})-(n-1)+1\le e(I_{2^{n-1}})$. The $n=1$ case was already handled. Since compression never decreased edges, every original family has at most the initial segment's edge count. This proves the theorem, including the exceptional terminal configuration rather than assuming all compressed families are initial segments.

For the remaining requests it is useful to obtain the entropy proof of cube edge-isoperimetry, including its equality cases. Inductively a family of size $m$ satisfiesIndeed let the two sections have sizes $a\ge b\ge 0$, $m=a+b>0$. Their internal edges are bounded inductively and the crossing edges are at most $b$, soHere $0{\log }_{2}0=0$ and $H_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ is the binary entropy function. Its concavity and its endpoint values at zero and one-half give $H_2(t)\ge 2t$ for $0\le t\le 1/2$. This proves the bound, starting from the zero-dimensional cube.

Define the isoperimetric number of a graph bySince every cube vertex has degree $n$, the internal-edge bound giveswhen $|A|\le 2^{n-1}$. A coordinate half-cube has one crossing edge per vertex, attaining ratio one. Hence, for $n\ge 1$,

Now establish the equality cases of entropy cube edge-isoperimetry. Strict concavity of $H_2$ makes $H_2(t)>2t$ for $0<t<1/2$. Equality in the internal-edge bound therefore requires either one section to be empty, or two equal-size sections. In the equal-size case equality in the crossing bound forces the sections to coincide; each section must also attain its inductive internal-edge bound. Induction gives exactly coordinate subcubes: the empty-section case fixes the coordinate, and the coincident-section case frees it. Conversely every coordinate subcube attains that bound.

At size $m=2^{n-1}$, an edge boundary of size $m$ means $e(A)=\frac{1}{2}m(n-1)=\frac{1}{2}m{\log }_{2}m$, so these equality cases apply. The subcube has dimension $n-1$ and fixes precisely one coordinate. ThereforeThese $2n$ coordinate half-cubes are the only extremizers of the requested size.

A well-order is a linearly ordered set in which every nonempty subset has a least element. First note that a well-order cannot be isomorphic to a proper initial segment of itself: the least element moved by such an isomorphism would have exactly the same predecessor set on each side, forcing it to be fixed. The same least-disagreement argument makes an isomorphism between initial segments unique.

Match $a\in A$ to $b\in B$ exactly when their strict predecessor sets are order-isomorphic. The preceding observation makes each match unique. Matches preserve order and fill initial segments on both sides, since restricting an isomorphism matches every earlier element. If both sides had an unmatched element, take the least unmatched $a$ and $b$. Their predecessor sets would be exactly the already matched segments, so they too would match, a contradiction. Therefore the matching exhausts at least one well-order and gives an isomorphism of that whole set onto an initial segment of the other. Uniqueness follows from the same predecessor-set argument. The whole set is allowed as an initial segment; this includes equal order types.

For ordinal division, let $\beta >0$ and chooseThis supremum is a set ordinal because $\beta \eta \ge \eta$ bounds the displayed ordinals by $\alpha$. Strict increase and continuity of multiplication in the right argument imply $\beta \gamma \le \alpha <\beta (\gamma +1)$. Take the order type $\delta$ of the remaining tail of $\alpha$ after its initial segment of type $\beta \gamma$. Then $\alpha =\beta \gamma +\delta$; if $\delta \ge \beta$ it would contradict the strict upper inequality. ThusThe half-open intervals $[\beta \eta ,\beta (\eta +1))$ are disjoint, so $\gamma$ is unique, and uniqueness of the tail gives uniqueness of $\delta$. This is left-divisor ordinal division: the order of multiplication cannot be interchanged.

Apply it with $\beta =\omega$. The remainder is finite. A nonzero remainder makes $\omega \gamma +\delta$ a successor, while a nonzero $\omega \gamma$ is a limit: for successor $\gamma$ it ends in a full block of type $\omega$, and for limit $\gamma$ it is the supremum of the earlier blocks. Consequently

The induced ordering on $x$ is a well-order. By transfinite recursion define $h(t)=\{h(s):s\in x,s<t\}$ for $t\in x$. Induction shows that each $h(t)$ is an ordinal, that these values strictly increase, and that their range is the ordinal $\mu (x)={\bigcup }_{t\in x}(h(t)+1)$. The map $h$ is an order isomorphism from $x$ to this ordinal. Any order isomorphism between ordinals must fix their elements successively, so this ordinal is unique.

An increasing map $j:\kappa \to \lambda$ between ordinals satisfies $j(\xi )\ge \xi$ by induction: its predecessors include $j(\eta )$ for all $\eta <\xi$. Hence $\kappa \le \lambda$. Apply this to the inclusion $x\subset y$, transported through their order isomorphisms, and then to $y\subset \alpha$. It follows that $\boxed{\mu (x)\le \mu (y)\le \alpha }$.

If each $x_n$ is an initial segment of later $x_m$, uniqueness makes their ordinal enumerations compatible: the enumeration of $x_m$ restricts to that of $x_n$. Their union is consequently an order isomorphism from ${\bigcup }_n{x}_n$ to ${\bigcup }_n\mu (x_n)$. This proves the asserted equality. Without the initial segment condition it fails: in $\alpha =\omega +1$, take $x_n=\{0,\dots ,n-1\}\cup \{\omega \}$. Then $\mu (x_n)=n+1$, whose union is $\omega$, but $\mu ({\bigcup }_n{x}_n)=\omega +1$.

For decreasing sets, $\mu (x_n)$ is a nonincreasing sequence of ordinals. Its set of values has a least member, attained at some $n_0$; all later values must equal it. Hence the sequence is eventually constant. The intersection formula nevertheless fails: take $x_n=\{n,n+1,\dots \}\subset \omega$. Every $x_n$ has order type $\omega$, whereas their intersection is empty and has order type zero. Thus $\mu ({\bigcap }_n{x}_n)=0\ne {\bigcap }_n\mu (x_n)=\omega$.

For $n\ge 1$, let $C_n=\{Z\in X:n\notin Z\}$. The presence or absence of $n$ is determined by a sufficiently long finite initial segment, so $C_n$ and its complement are open sets in the ordinary topology on infinite subsets. The Ellentuck topology is finer, hence each $C_n$ is star-clopen and in particular star-closed. Their union isEvery basic star-neighborhood $[s,A]$ of $\mathbb{N}$ has $s=\{1,\dots ,k\}$ for some $k\ge 0$, and its reservoir $A$ contains every integer greater than $k$. Choosing $n>k$ gives $\mathbb{N}\setminus \{n\}\in [s,A]\cap C_n$. Thus $\mathbb{N}$ is in the star-closure of the union, but not in the union itself. Therefore

Take $\tau$ to be the ordinary topology on infinite subsets, whose basic cylinders $[s]$ fix a finite initial segment. LetThis is a dense countable family of cofinite infinite subsets. It is countable because finite complements form a countable family. Each singleton is $\tau$-closed: distinct increasing enumerations differ at some finite coordinate, which separates them by cylinders. No singleton has interior, since every cylinder admits more than one infinite continuation. Thus every singleton is $\tau$-nowhere dense, and $D$ is $\tau$-meagre.

On the other hand, every cylinder $[s]$ contains the cofinite set $s\cup \{n:n>\max s\}$, with $\max \varnothing =0$. Hence $D$ is $\tau$-dense, its closure is all of $X$, and

The paper does not define its symbol $\tau$. If the course instead uses it for the Ramsey cone topology, with basic neighborhoods $[A{]}^{\omega }$ and no finite stem, use $X$ itself as the example. For $D_j=\{Z:\min Z=j\}$, its cone-closure is $\{Z:j\in Z\}$: every cone neighborhood of a set containing $j$ contains an infinite subset of minimum $j$, while a cone based on a set omitting $j$ misses $D_j$. This closure has empty interior, because every infinite reservoir can be thinned to omit $j$. Thus every $D_j$ is cone-nowhere dense, and $X={\bigcup }_{j\ge 1}{D}_j$ is cone-meagre but is not cone-nowhere dense. This supplies the requested example under either convention, without conflating the two topologies.

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

Use the external external vertex boundary conventionEquivalently, its closed graph neighbourhood is $N[\mathcal{A}]=\mathcal{A}\cup B(\mathcal{A})$. Some boundary conventions use this closed graph neighbourhood itself; because the compared set families have equal size, either convention gives the same inequality.

Order the Boolean lattice first by increasing size, and within a size by lexicographic order, with the smallest differing coordinate in the earlier set. If $I$ is the initial segment in this simplicial order on the discrete cube with $|I|=|\mathcal{A}|$, Harper inequality isIn particular, writing $S_n(t)={\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, if $|\mathcal{A}|\ge S_n(t)$ then $|N[\mathcal{A}]|\ge S_n(t+1)$.

Here is the full simplicial section compression proof. The cases $n=0,1$ are immediate. A simplicial initial segment has an initial-segment closed graph neighbourhood: it contains every smaller level, and its remaining upper level is the upper shadow of a lexicographic initial segment. That upper shadow is lexicographic initial because a set has a face in the segment exactly when its earliest face does, and earliest faces preserve lexicographic order.

Assume the result in dimension $n-1$. For a coordinate $i$, delete it from the present section and write the two sections as ${\mathcal{A}}_0,{\mathcal{A}}_1$. Their neighbourhood sections are exactlyReplace both sections by equally large simplicial initial segments $I_0,I_1$. The mathematical induction hypothesis controls each internal neighbourhood. Both sets in each new union are initial segments, so that union has size equal to the larger of their sizes. The corresponding old union has at least that size. Therefore this simplicial section compression does not enlarge $N[\mathcal{A}]$.

Repeatedly compress any noninitial section. Every change strictly reduces the sum of the global simplicial positions of the set family members, so the process terminates at a set family $\mathcal{C}$ compressed in every section. Suppose an earlier vertex $X$ is missing while a later vertex $Y$ is present. If they agree in any coordinate, they contradict compression of that coordinate's section. Thus $Y=[n]\setminus X$. They must also be consecutive in simplicial order: an intermediate vertex, whether present or absent, would create another inversion and would have to equal one of these two complementary vertices. No other inversion is possible for the same reason. Hence $\mathcal{C}$ is either the required initial segment or that segment with its last vertex $X$ exchanged for the next vertex $Y$, with $X,Y$ complementary.

For completeness, these terminal families for simplicial section compression can be checked explicitly. If $n=2k+1$, the exceptional consecutive vertices are the last $k$-set $X=\{k+2,\dots ,2k+1\}$ and first $(k+1)$-set $Y=\{1,\dots ,k+1\}$. For $k\ge 1$, the initial segment is all levels through $k$. After the exchange every vertex of size at most $k+1$ is still in its closed graph neighbourhood: a $(k+1)$-set has at least two $k$-faces, so deleting the one face $X$ cannot remove it, and $X$ itself neighbours a retained smaller set. Thus the new neighbourhood contains the old one. For $k=0$, the two single-vertex set families have the same neighbourhood.

If $n=2k$, the exceptional pair is $X=\{1,k+2,\dots ,2k\}$ and $Y=\{2,\dots ,k+1\}$. The initial segment consists of every level below $k$ and all $k$-sets containing coordinate one. Its closed graph neighbourhood consists of every level through $k$ and the $(k+1)$-sets containing coordinate one. For $k\ge 2$, each of the latter has $k\ge 2$ faces containing coordinate one, so deleting $X$ removes no such neighbour. Every lower level remains covered. For $k=1$, the added vertex $Y$ itself keeps the sole two-element neighbour covered. Again the exchange does not decrease the neighbourhood. These are the only complementary consecutive pairs, as is seen by checking the central ranks and the lexicographic transition between middle-rank sets containing and avoiding coordinate one.

We have reached a set family whose neighbourhood is at least the initial segment's, without increasing the original neighbourhood. This proves Harper inequality by mathematical induction, including the exceptional compressed set families often omitted from the argument.

For the final request, the usual two-coordinate shift does not increase the boundary of a uniform set family. To see this carefully, let $i\ne j$ and let $C_{ij}$ move a set containing $j$ but not $i$ to its partner with $j$ replaced by $i$, only if that partner is absent. For any uniform set family $\mathcal{F}$,Here is the local witness check for the lower shadow inclusion. A shadow member containing neither or both of $i,j$ has an old witness after possibly exchanging $i,j$ in that witness. For a paired shadow vertex containing $i$ only, either its old version or its $j$-partner has an old witness, which suffices for its membership in the shifted shadow. For a vertex containing $j$ only that survives in the new shadow, its new witness either contains both coordinates, supplying both old shadow partners directly, or is an unshifted $j$-only witness whose $i$-partner was already present. In either event both old shadow partners existed, which is exactly the condition for the $j$-vertex to survive the shadow shift. This exhausts the coordinate patterns.

Taking complements converts an upper shadow into a lower shadow and converts $C_{ij}$ into $C_{ji}$, proving the second inclusion. Each shift preserves cardinality on the shadow level. The external boundary of an $r$-uniform set family is the disjoint union of its lower and upper shadows, soThe endpoint levels $r=0,n$ have an empty shadow on one side and obey the same conclusion.