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

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.

In a set family, replace a set containing $i$ by its deletion of $i$ only when that deletion is absent. This preserves cardinality and cannot increase maximum pairwise Hamming distance. If a new set and a retained set gave a larger distance, the retained set's deletion would already have been present; that deletion and the original uncompressed set would give the same distance. Repeated downward compressions yield a down-set.

For a down-set $D$ in the Boolean lattice, every member $A$ has all its $|A|$ immediate lower neighbors in $D$. Counting an internal edge at its upper endpoint gives $e(D)={\sum }_{A\in D}|A|$. The degree identity for the edge boundary of the hypercube graph then gives the displayed formula.

For a nonempty degree-$m$ layer of a down-set in an $N$-element Boolean lattice, the unique real number $x_m\ge m$ with $|{\mathcal{F}}_m|=\left(\genfrac{}{}{0ex}{}{x_m}{m}\right)$ measures an effective number of available coordinates. The Lovász shadow bound and $\partial {\mathcal{F}}_{m+1}\subseteq {\mathcal{F}}_m$ imply $x_{m+1}\le x_m$ whenever the later layer is nonempty. It is a real parameter, not the actual size of the set family's support.

For a down-set of size $m$, maximize its edge boundary by minimizing the sum of the sizes of its members. Choose all sets in the smallest ranks, followed by any needed part of the next rank; this minimizes that sum among all families and is itself a down-set. With $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, $M_{-1}=0$, and $M_{r-1}\le m\le M_r$, the exact maximum is $h(m)=nm-2[{\sum }_{j<r}j(\genfrac{}{}{0ex}{}{n}{j})+r(m-M_{r-1})]$.

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.

View a set family as a set of vertices of the Boolean lattice. The operation $D_i$ acts independently on each pair $\{S,S\cup \{i\}\}$, where $i\notin S$: it keeps a full or empty pair and moves a sole upper member down. Thus downward coordinate compression preserves cardinality.

Fix a tracing set $Y$. If $i\notin Y$, compression leaves the trace of a set family on $Y$ unchanged. If $i\in Y$, write $B_0,B_1\subseteq \mathcal{P}(Y\setminus \{i\})$ for the two sections of the old trace, according to absence or presence of $i$. The absent-$i$ section of the new trace is $B_0\cup B_1$. Its present-$i$ section is contained in $B_0\cap B_1$: an upper member survives only when its lower partner was also present in the original family. ConsequentlyIn particular, downward coordinate compression cannot create new set shattering.

Repeatedly apply any changing downward coordinate compression. Each change strictly decreases ${\sum }_{A\in \mathcal{F}}|A|$, so the process terminates at a down-set $\mathcal{D}$ with the same cardinality and with no larger trace on any $Y$. The Sauer-Shelah lemma says that a family shattering no $k$-element set satisfiesIndeed, the compressed down-set also shatters no $k$-element set. If it contained any member of size at least $k$, all subsets of a $k$-subset of that member would belong to the down-set, contradicting this restriction. Every member therefore has size at most $k-1$, giving the bound. Equivalently, VC dimension at most $d$ gives size at most ${\sum }_{j=0}^d\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The family of all sets of size at most $d$ attains this bound.

There is a different extremal example when $n\ge 3$. Toggle a fixed coordinate in the family of sets of size at most two:The symmetric difference is a bijection, so this family has $1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. On each tracing set $Y$, it simply toggles coordinate $1$ if $1\in Y$; thus it preserves trace cardinality and set shattering. A triple has seven trace patterns, not eight. The new family differs from the original one because it contains $\{1,2,3\}$. For $n\le 2$ the specified cardinality is $2^n$, so the entire power set is the unique family of that size; the different example requires $n\ge 3$.

For the final bound, let $e_i(\mathcal{F})$ count pairs $S,S\cup \{i\}$ both in the family. Deleting coordinate $i$ identifies precisely these pairs, soSuppose every deletion lost at least two members, so $e_i(\mathcal{F})\ge 2$ for every $i$. The trace inequality and preservation of cardinality show that $e_i(\mathcal{D})\ge e_i(\mathcal{F})$ after downward coordinate compression. The down-set $\mathcal{D}$ contains the empty set and every singleton. For each $i$, its second edge in direction $i$ has an upper endpoint of size at least two. Downward closure then supplies a pair $\{i,j\}\in \mathcal{D}$. The pairs in $\mathcal{D}$ therefore cover all $n$ coordinates, so at least $\lceil n/2\rceil$ pairs are needed. This proves two cube edges in every direction force many vertices:Taking the contrapositive gives the required answer:The threshold is sharp for every $n\ge 2$. Take the empty set, all singletons and $\lceil n/2\rceil$ pairs covering every coordinate. For even $n$, use the disjoint pairs $12,34,\dots ,(n-1)n$; for odd $n$, pair the first $n-1$ coordinates and add $(n-1)n$. This down-set has exactly $\lceil 3n/2\rceil +1$ members and at least two edges in every direction, so every $(n-1)$-coordinate trace has size at most $|\mathcal{F}|-2$. Adding further members preserves those pairs and therefore preserves the failure whenever a larger cardinality is feasible. For $n=1$, the putative counterexample cardinality is three, exceeding the size of the Boolean lattice; the sharpness construction naturally starts at $n=2$.

Assume first $1\le t\le n$, and write $d=n-t$. The sharp nonuniform t-intersecting family bound isWe prove the bound by deriving the needed Kleitman diametric theorem. Identify subsets with binary words, with Hamming distance $|A△B|$. Let $D(n,d)$ be the two expressions above. A set family of Hamming diameter at most $d<n$ has size at most $D(n,d)$, as follows.

First apply downward coordinate compression: delete coordinate $i$ from a member only when its deletion is not already present. This preserves size and cannot increase the Hamming diameter. The only possible increased distance would be between a newly lowered member $A\setminus \{i\}$ and a retained member $B$ containing $i$. The deletion $B\setminus \{i\}$ must have belonged to the old set family, or $B$ would have been lowered too. The old pair $A,B\setminus \{i\}$ has precisely that increased distance, proving it was already allowed. Repeated downward compressions terminate in a down-set.

Next apply all elementary set shifts $S_{ij}$ with $i<j$. They preserve size and Hamming diameter. If shifting one member but retaining the other increased their distance, the retained member must contain $j$ but not $i$; its shifted partner was already present, and the old pair with that partner has the same distance. These shifts preserve the down-set property: a subset of a shifted member either was already present or is obtained by shifting its corresponding old subset. For a retained member, a subset cannot disappear, because the shifted partner of that subset is also a subset of the member or of its retained shifted partner. Repeated shifts terminate, since the sum of the selected coordinate labels decreases whenever a change occurs. We now have a shifted down-set $\mathcal{F}$ of the same size and Hamming diameter.

Split it into sections on $[n-1]$:The first section has Hamming diameter at most $d$. We claim the second has Hamming diameter at most $d-2$. For $X,Y\in {\mathcal{F}}_1$, downward closure gives $X\setminus Y,Y\in {\mathcal{F}}_1$. Compare $(X\setminus Y)\cup \{n\}$ with $Y\in {\mathcal{F}}_0$. Their distance is $|X\cup Y|+1$, so $|X\cup Y|\le d-1<n-1$. Choose $i<n$ outside their union. Shiftedness puts $X\cup \{i\}$ in ${\mathcal{F}}_0$, while $Y\cup \{n\}$ is a member of $\mathcal{F}$. Their distance is $|X△Y|+2$, proving the claim. For $d<2$ this argument forces ${\mathcal{F}}_1$ to be empty.

The induction now giveswhere negative-diameter set families are empty. The equality of the numerical expressions is Pascal's identity. The base case $d=0$ has at most one member. At the boundary $d=n-1$, at most one member of each complementary pair is allowed, giving $2^{n-1}$, which equals $D(n,n-1)$ by binomial symmetry. For the remaining cases $1\le d\le n-2$, both section bounds belong to smaller-dimensional induction cases. This completes the diametric proof.

For a $t$-intersecting set family,so the theorem applies. For $d=2q$, equality is attained by all sets of size at least $n-q$, since two such sets intersect in at least $n-2q=t$ elements. For $d=2q+1$, take all sets of size at least $n-q$, and also all $(n-q-1)$-sets avoiding one fixed point. Two of these smaller sets intersect in at least $2(n-q-1)-(n-1)=t$ points; a smaller and a larger set intersect in at least $t$; two larger sets intersect in at least $t+1$. The size of this set family isso it attains the odd bound. If $t=0$, the full power set is admissible; if $t>n$, the only admissible set family is empty.

Every maximal 1-intersecting set family attains $2^{n-1}$, for $n\ge 1$. Such a set family is an up-set, since adding a superset preserves set intersections. It contains $[n]$ and omits the empty set. It contains at most one member of any complementary pair. If neither of two nonempty complements $A,A^c$ were present, maximality would give a member $B$ disjoint from $A$; upward closure would then include $A^c$, a contradiction. Thus it chooses precisely one member of each complementary pair, as in maximal intersecting families choose one member of every complementary pair.

Not every maximal 2-intersecting set family attains the bound. On four points, let $\mathcal{A}=\{A:\{1,2\}\subseteq A\}$. This set family has four members and is maximal: every missing set meets its member $\{1,2\}$ in at most one point. The sharp bound is $1+4=5$, attained by all sets of size at least three. This proves maximal intersection does not imply maximum size.

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 cube vertices with subsets of $[n]$. In a down-set $D$, every $A\in D$ has all its $|A|$ immediate lower neighbors in $D$. Counting each internal edge by its upper endpoint gives the edge boundary of a down-set in a cubeTo maximize it, minimize the sum of set sizes. Among all families of $m$ sets, the minimum is obtained by taking the smallest ranks first. This choice is a down-set: take every set of size below $r$, followed by any required selection of $r$-sets.

Write $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, with $M_{-1}=0$, and choose $r$ such that $M_{r-1}\le m\le M_r$. The largest edge boundary of a down-set is thereforeEquivalently, it is ${\sum }_{j<r}(n-2j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)+(n-2r)(m-M_{r-1})$. This includes $m=0$ and $m=2^n$, with boundary zero. If $m$ is exactly a complete-level size, either adjacent choice of $r$ gives the same value.

A down-set in the Boolean lattice is a family closed under taking subsets. Restricting the minimization to down-sets cannot decrease the minimum from the edge-isoperimetric inequality in the discrete cube.

The coordinate subcube consisting of all subsets of a fixed $k$-element set is itself a down-set and attains that minimum. Thus

Give a vertex $S\subseteq [n]$ the binary value $\nu (S)={\sum }_{i\in S}{2}^{i-1}$. The binary order on the discrete cube orders vertices by increasing $\nu$; its initial segment $I_m$ consists of the values $0,\dots ,m-1$. Write $e(\mathcal{A})$ for the number of cube edges whose two endpoints lie in $\mathcal{A}$, and ${\partial }_e\mathcal{A}$ for its external edge boundary. The degree sum identity isThe exact edge-isoperimetric inequality iswhere $\mathrm{wt}(j)$ is the number of ones in the binary expansion of $j$. Equality is attained by $I_m$. Indeed, $I_m$ is a down-set, so every downward neighbour of each vertex is also present. Counting each internal edge at its upper endpoint gives $e(I_m)={\sum }_{j<m}\mathrm{wt}(j)$. We prove the equivalent edge-isoperimetric theorem for binary initial segments, $e(\mathcal{A})\le e(I_m)$, by mathematical induction using section compression in binary order.

Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the two sections with coordinate $i$ absent or present, deleting that coordinate. Their inherited binary order is the binary order on the remaining coordinates. Replace each section by the binary initial segment of its own size. This preserves $|\mathcal{A}|$. The edges split into internal edges in the two sections and crossing edges, givingBy the mathematical induction hypothesis, the two section edge counts do not decrease. After compression, the sections are nested initial segments, so their intersection has the largest possible size, $\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. Thus each section compression does not decrease the internal edge count.

Apply these compressions repeatedly whenever one changes the family. The integer potential ${\sum }_{S\in \mathcal{A}}\nu (S)$ decreases strictly at every nontrivial step: within either fixed-coordinate section, the initial segment uniquely minimizes the sum of the vertex values among sets of the prescribed size. Therefore the process terminates with a family compressed in every section.

We need a small structural fact about families compressed in every binary section. If such a family is not a binary initial segment, choose a missing vertex $x$ and a present vertex $y$ with $\nu (x)<\nu (y)$. They cannot agree in any coordinate: in that coordinate's section, the compressed initial segment would contain $x$ whenever it contains $y$. Thus $y=[n]\setminus x$. The same argument applies to every inversion. There cannot be any vertex strictly between $x$ and $y$ in binary order: a present one would form an inversion with $x$, and a missing one would form an inversion with $y$, forcing it to be $y$ or $x$, respectively. Hence $\nu (y)=\nu (x)+1$. Together with $\nu (x)+\nu (y)=2^n-1$, this givesEvery vertex below $x$ must be present, and every vertex above $y$ absent, by the same inversion argument. Therefore the only possible exception to a binary initial segment isFor $n\ge 2$, this replaces the top vertex of an $(n-1)$-dimensional subcube by the singleton $\{n\}$. Removing that vertex loses $n-1$ internal edges, and adding the singleton creates exactly one edge, to the empty set. ThusThe dimensions $n=0,1$ are immediate. This finishes the mathematical induction: compression leads either to the desired initial segment or to an exception with no larger edge count. Hence the exact edge-isoperimetric inequality in the discrete cube holds, and binary initial segments maximize the number of contained edges at every size.

For the square-face assertion, let $f(\mathcal{A})$ count the two-dimensional cube faces all of whose vertices are in $\mathcal{A}$. We use mathematical induction again, now also using the edge theorem just proved. Faces lying wholly in one coordinate section contribute $f({\mathcal{A}}_0)+f({\mathcal{A}}_1)$. Every face crossing coordinate $i$ is determined by an edge lying in both sections, soCompress the two sections as before. Their internal face counts do not decrease by mathematical induction. Put $c=|{\mathcal{A}}_0\cap {\mathcal{A}}_1|$ and $b=\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. The edge theorem and nesting of binary initial segments giveAfter compression, the intersection is precisely $I_b$. Thus section compression does not decrease the face count either. The same decreasing potential gives termination, and the same classification leaves only a binary initial segment or ${\mathcal{E}}_n$.

In the exceptional family, removing the top vertex loses $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ square faces, one for each pair of downward coordinate directions. The added singleton lies in no square face, because it is the only vertex in its upper section. ConsequentlyDimensions below two have no square faces and start the mathematical induction. We have proved that binary initial segments maximize contained square faces:For an explicit value, the down-set property counts every face at its unique top vertex, givingThis establishes binary initial segments maximize contained square faces for arbitrary sizes, rather than only sizes that are powers of two.