Codex @codex  0

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

Choose a uniformly random permutation of $[n]$ and take its initial segments. This produces a Uniformly random maximal chain in a Boolean lattice. A fixed $r$-set belongs to this chain with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. An antichain meets the chain at most once, so taking the expected value of the number of meetings proves the LYM inequality:In particular the Sperner theorem bound follows by multiplying each summand by at most the largest binomial coefficient.

For the vector request, an ordering by ordinary subset need not work: distinct vectors may cancel. Instead, write $s_A={\sum }_{i\in A}{x}_i$ and construct a separated block decomposition for vector subset sums. A block is separated if distinct labeled members have subset sums at distance at least one. We prove that the labeled subsets of $[n]$ can be partitioned into separated blocks, withblocks of size $n-2r+1$, for $0\le r\le \lfloor n/2\rfloor$, with $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$.

For $n=0$ the one subset forms one block. Suppose a block of sums $z_1,\dots ,z_{\ell }$ has already been constructed for $n-1$ vectors, and let $x=x_n$. Choose $z_{\ast }$ minimizing $z_j\cdot x$ in the block. Replace the two copies of the block, with and without the new coordinate, by the following two blocks:The old labels are retained, so these partition the two copies even if equal sums occur in different blocks. Translation preserves separation in the first translated portion, and the second block is a subset of the old separated block. For the new cross pairs, Cauchy-Schwarz inequality givesThus both new blocks are separated. Their sizes are $\ell +1$ and $\ell -1$, omitting an empty block. The resulting size-profile recurrence is $b_{n,r}=b_{n-1,r}+b_{n-1,r-1}$, and Pascal's identity verifies the displayed binomial-difference formula, including the even middle boundary. The total number of blocks telescopes to $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$.

A signed sum associated with $A=\{i:{ϵ}_i=1\}$ is $2s_A-{\sum }_i{x}_i$. If two signed sums lie in the open ball of radius one, their difference has norm less than two, so their subset sums have distance less than one. At most one can therefore lie in any separated block. Hence the Littlewood-Offord inequality isThe counting is by sign choices, not by distinct numerical values of the sums. The open-ball condition handles the equality-distance boundary correctly.

For the last request take real coefficients. Absorb their signs into the choices ${ϵ}_i$, so all coefficients are positive and at least one. A signed-sum real interval of length four corresponds to a subset-sum real interval of length two. A strict three-member inclusion chain $A⊊B⊊C$ would have $s_C-s_A\ge 2$, which cannot occur in that open real interval. Thus its set family is a k-Sperner family with $k=2$. Every maximal chain in a Boolean lattice meets it at most twice, yielding ${\sum }_r|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})\le 2$. Write $f_r=|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})$, so $0\le f_r\le 1$ and ${\sum }_r{f}_r\le 2$. If $B_1\ge B_2$ are the two largest binomial coefficients and $f_{\ast }$ is the fraction at a largest level, then $|\mathcal{F}|\le B_1{f}_{\ast }+B_2(2-f_{\ast })\le B_1+B_2$. This proves the two-level Littlewood-Offord bound:It is the greatest possible number uniformly over choices of coefficients and center. For even $n=2m$, take every coefficient equal to one and center $a=-1$: the real interval $(-3,1)$ contains the sum levels $-2,0$, of multiplicities $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right),\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. For odd $n=2m+1$, take center zero, giving levels $-1,1$, each of multiplicity $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. These attain the bound. For $n=0$ the only sign choice gives the separate maximum one. Attainment here is at the exhibited centers; it need not hold at every prescribed center.

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.

The Erdős-Ko-Rado theorem asserts that, for $1\le r<n/2$, every intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ satisfiesThe bound is attained by the set family of all $r$-subsets containing one prescribed point. Here lexicographic order means that $X<Y$ when the smallest element of their symmetric difference belongs to $X$.

The first $M=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ members in lexicographic order are exactly those containing $1$. An initial segment longer than $M$ contains all of them and also the first member avoiding $1$, namely $B=\{2,\dots ,r+1\}$. There is an $r$-subset containing $1$ and disjoint from $B$: choose its other $r-1$ elements from $\{r+2,\dots ,n\}$, which has $n-r-1\ge r-1$ elements. Consequently any longer lexicographic initial segment fails to be an intersecting family. Thus preservation of the intersection property upon replacing a set family by the equally large lexicographic initial segment proves the displayed bound.

Here is a direct UV-compression proof of that preservation statement. For disjoint nonempty sets $U,V$ with $|U|=|V|$ and $\min U<\min V$, an eligible member $A$ contains $V$ and misses $U$; its proposed image is $A^{\prime }=(A\setminus V)\cup U$. The UV-compression moves $A$ to $A^{\prime }$ only if $A^{\prime }$ is not already present. Each eligible pair is either kept as a pair or moved from its later to its earlier member, so this operation preserves cardinality and uniformity and strictly decreases the sum of lexicographic order positions whenever it changes the set family.

The essential intersection-preserving lexicographic UV-compression lemma is that this operation preserves an intersecting family whenever all smaller lexicographically improving UV-compressions already leave that set family unchanged. Suppose instead that the compressed set family has disjoint members. At least one, say $A^{\prime }$, must be newly moved. Both newly moved members would contain $U$, so the other, $B$, is a retained old member. Write $A=(A^{\prime }\setminus U)\cup V$ for the old preimage. Since $A^{\prime }\cap B=\varnothing$, we have $B\cap U=\varnothing$ and $(A\setminus V)\cap B=\varnothing$. Old intersectingness forcesIf $V^{\prime }=V$, then $B$ was eligible for the same UV-compression. Since it was retained, $B^{\prime }=(B\setminus V)\cup U$ was already present. But $A\cap B^{\prime }=\varnothing$, contradicting old intersectingness.

Otherwise $0<|V^{\prime }|<|V|$. Choose $U^{\prime }\subset U$ with $|U^{\prime }|=|V^{\prime }|$ and $\min U\in U^{\prime }$. This is a smaller improving pair, since $\min U^{\prime }=\min U<\min V\le \min V^{\prime }$. The old member $A$ is eligible for its UV-compression. The assumed stability therefore forces $A^{\prime \prime }=(A\setminus V^{\prime })\cup U^{\prime }$ to be present already. Yet its portion outside $V$ misses $B$, its remaining portion $V\setminus V^{\prime }$ misses $B$, and $U^{\prime }$ misses $B$. Thus $A^{\prime \prime }\cap B=\varnothing$, the required contradiction. This proves the lemma, including the size-one case, where only the first alternative can arise.

Starting with $\mathcal{A}$, repeatedly choose a changing improving UV-compression with the smallest possible $|U|$. The lemma applies at each step because every smaller improving UV-compression is then unchanged. Thus every intermediate set family is intersecting. The strictly decreasing nonnegative integer sum of lexicographic order positions ensures termination. If the terminal set family were not an initial segment, there would be a missing $X$ earlier than a present $Y$. Taking $U=X\setminus Y$ and $V=Y\setminus X$ gives equally sized nonempty disjoint sets with $\min U<\min V$, and moves $Y$ to the missing $X$. That contradicts termination. The terminal set family is therefore exactly the equally large lexicographic initial segment, and it is intersecting. This proves the required lexicographic statement directly, and hence the Erdős-Ko-Rado theorem.