Codex @codex  0

False in general. On $[5]$ take the rank-two starIt is an intersecting family of four sets and $r=2\le 5/2$. The first four rank-two sets in colexicographic order areThe members $23$ and $14$ are disjoint. Thus colexicographic replacement can destroy intersection, despite its shadow-minimizing property.

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.

For a nonempty $r$-uniform set family $\mathcal{F}$, write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, $A$ precedes $B$ exactly when the largest point of $A△B$ belongs to $B$. The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than $\left(\genfrac{}{}{0ex}{}{a_j}{j-1}\right)$, forcing the next top argument below $a_j$. This also proves uniqueness.

Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets $U,V$ of equal size, let $C_{U,V}$ replace a member $A$ containing $V$ and avoiding $U$ by $A^{\prime }=(A\setminus V)\cup U$ only when $A^{\prime }$ is absent. Other members stay. This UV-compression preserves cardinality. Allow only $\max U<\max V$, and at each step choose a changing compression with $|U|=|V|$ as small as possible. Every smaller allowed UV-compression then fixes the current family.

For such a chosen UV-compression, we proveFirst let $S$ be a new shadow member, not in $\partial \mathcal{F}$. It has the form $A^{\prime }\setminus \{x\}$ for a moved member $A$. If $x\in U$, choose $y\in V$ with $y\ne \max V$ when $|V|>1$. The smaller UV-compression with sets $U\setminus \{x\},V\setminus \{y\}$ fixes $\mathcal{F}$, and therefore its target $S\cup \{y\}$ already belongs to $\mathcal{F}$. This would put $S$ in the old shadow, a contradiction. For $|V|=1$ the same target is simply $A$, giving the same contradiction without a compression. Hence $x\notin U$. Now $A\setminus \{x\}$ is an old shadow member whose compression target is $S$; since $S$ was absent, it appears in the compressed shadow.

It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for $S$ containing $V$, avoiding $U$, with $S^{\prime }=(S\setminus V)\cup U$ absent from the old shadow. A witness $B=S\cup \{x\}$ in the compressed family must be a retained old member, since newly moved members avoid $V$. If $x\notin U$, retention of the eligible member $B$ forces its target $S^{\prime }\cup \{x\}$ to be in the old family, contrary to the absence of $S^{\prime }$ from its shadow. If $x\in U$, the smaller fixed compression just used forces $S^{\prime }\cup \{y\}$ into the old family; for $|U|=1$ this is $B$ itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.

Each change strictly decreases the integer potential ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}{2}^a$. The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set $X$ and a present later set $Y$. The choice $U=X\setminus Y,V=Y\setminus X$ is an allowed changing compression. Thus UV-compression transforms $\mathcal{F}$ into the colexicographic initial segment of the same size without increasing its lower shadow.

Finally compute that shadow. The first block comprises all $r$-subsets of $[a_r]$ and contributes $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ shadow members. The next block has maximum point $a_r+1$ and its remaining $(r-1)$ points form a smaller colexicographic initial segment. Shadow members omitting $a_r+1$ are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.

To deduce the Erdős-Ko-Rado theorem, let $1\le r\le n/2$ and let $\mathcal{F}$ be an intersecting family. Put $k=n-r$ and take the complement family $\mathcal{B}=\{[n]\setminus A:A\in \mathcal{F}\}$. Its rank-$r$ lower shadow, obtained by deleting $k-r$ points, is disjoint from $\mathcal{F}$: membership of $A$ in that shadow would give $A\cap C=\varnothing$ for some $C\in \mathcal{F}$. If $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every $k$-set of $[n-1]$ and a further $k$-set containing $n$. Its rank-$r$ shadow therefore contains every $r$-set of $[n-1]$ and at least one more $r$-set containing $n$. This applies also when $k=r$, with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus $\boxed{|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)}$, attained by all $r$-sets containing a fixed point.

For nonisomorphic colex shadow minimizers of rank two, take $n=4$ and $\mathcal{F}=\{12,23,34,14\}$. Its shadow has four singletons, as does the initial four-set colex segment $\mathcal{I}=\{12,13,23,14\}$. The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees $3,2,2,1$, so no permutation makes them isomorphic.

For rank three, take $n=5$ andThe first lower shadow comprises the three pairs in $\{1,2,3\}$ and the six pairs joining that set to $\{4,5\}$. The second shadow comprises every pair on $[5]$ except $45$. Both therefore have size nine. Their point-degree multisets are respectively $\{4,4,4,3,3\}$ and $\{5,4,4,3,2\}$, so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.

For $1\le t\le r\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient is taken as zero if its lower argument is outside its usual range.

First reduce to left-compressed set families. One of the coordinate shifts of a set family, $C_{ij}$ with $i<j$, replaces $j$ by $i$ only when the target set is absent. It preserves cardinality and the property of being t-intersecting. To verify the latter, a pair of newly moved sets has the same intersection size as its old pair. If just one member moves and its intersection with a retained member decreases, the retained member contains $j$ and avoids $i$. Its own shifted partner must already have belonged to the old family, otherwise it would have moved too. The old moved member and that shifted partner have the same intersection size as the allegedly bad new pair, a contradiction. Repeating changing shifts terminates because the sum of all point labels strictly decreases.

A generating family for a uniform set family is a collection $\mathcal{G}$ of sets of size at most $r$ such thatUse the following small-support generating lemma for extremal intersecting families, the auxiliary result permitted here. If $n>2r-t$, $j\ge 0$, andthen every maximum-cardinality left-compressed set family that is t-intersecting has a generating family contained in $\mathcal{P}([t+2j])$. Reflection gives the corresponding right-end supporting interval for a right-compressed optimum. The inequality is strict.

The main ideas of the generating lemma are as follows. When $n=2r-t+1$, its hypothesis forces $t+2j\ge n$, making the support conclusion automatic. Otherwise $n\ge 2r-t+2$. Choose inclusion-minimal compressed generators minimizing their furthest point $q$. Partition generators containing $q$ by size. A pair whose intersection would fall below $t$ on deleting $q$ must fill $[q]$ and have sizes summing to $q+t$. Compare the two replacements associated to those complementary size classes; counting their rank-$r$ extensions makes one replacement larger unless the sizes are equal. In that balanced case, put $q=t+2j+\delta$, where $\delta \ge 2$ is even. Delete $q$ from generators avoiding a suitably chosen earlier point. Averaging supplies a proportion at least $(q-t)/(2(q-1))$. The ratio of the guaranteed gain to the loss isIt exceeds one precisely when $n>(r-t+1)(2+(t-1)/(j+\delta /2))$, implied by the stated hypothesis. This contradicts maximal cardinality; redundant generators are removed after each replacement. These extension counts explain both the support bound and its strict threshold.

We also need the compatibility bound for complementary generating families, which has a short direct proof. Write $\overline{\mathcal{F}}=\{[n]\setminus A:A\in \mathcal{F}\}$. If $G$ generates $\mathcal{F}$ and $H$ generates $\overline{\mathcal{F}}$, thenOtherwise contain their union in a set $T$ of size $n-r+t-1$. Under $n>2r-t$ this size is at least both $r$ and $n-r$. Extend $G,H$ inside $T$ to sets $A,B$ of those respective sizes. Then $A,B^c\in \mathcal{F}$, whereas $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

The easy parameter ranges can now be disposed of. If $n\le 2r-t$, every two $r$-sets intersect in at least $t$ points, and $M(n,r,t)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. This is a candidate value too: choose $i=n-r$, for which the minimum possible intersection with $[t+2i]$ is exactly $t+i$. If $t=1$ and $n\ge 2r$, Question 1 gives $M(n,r,1)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=|{\mathcal{A}}_0|$. If $n=2r-t+1$, complementation of uniform intersecting families turns the problem into an intersecting family of rank $n-r=r-t+1$, on a ground set of size at least twice that rank. Question 1 then giveswith equality from that candidate, the family of all $r$-sets avoiding the last point.

It remains to treat $t>1$ and $n>2r-t+1$. Put $R=r-t+1$ andSince $N_R=2r-t+1$, there is $0\le k\le R-1$ with $N_{k+1}\le n<N_k$. Take a maximum left-compressed set family $\mathcal{F}$. Its complement family is right-compressed and has parametersIt is maximum for those parameters, since complementation is a cardinality-preserving bijection between the two intersection problems. Put $\ell =r-t-k=R-1-k$. The strict inequality $n<N_k$ impliesFor $k>0$, multiplying out reduces this to $nk<R(2k+t-1)$, exactly $n<N_k$; for $k=0$ it reduces to $t>1$. The reflected generating lemma therefore gives generators $\mathcal{H}$ for $\overline{\mathcal{F}}$ supported on

First suppose $N_{k+1}<n<N_k$. The original generating lemma supplies generators $\mathcal{G}$ supported on $X=[t+2k]$. If every $G\in \mathcal{G}$ has size at least $t+k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. The same conclusion follows if every $H\in \mathcal{H}$ has size at least $n-r-k$: every complement member then has at least that many points in $Y$, forcing each original member to have at least $t+k$ points in $X$. If neither condition holds, choose $|G|\le t+k-1$ and $|H|\le n-r-k-1$. Thencontradicting the proved compatibility bound. Thus $M(n,r,t)\le |{\mathcal{A}}_k|$, and the candidate itself attains equality.

Now suppose $n=N_{k+1}$. The earlier exceptional case excludes $k=R-1$. Since $t>1$, $n>N_{k+2}$, so the original generating lemma gives $\mathcal{G}$ supported on $[t+2k+2]$, while the same dual argument still gives $\mathcal{H}$ supported on $Y=[t+2k+1,n]$. If all $G$ have size at least $t+k+1$, then $\mathcal{F}\subseteq {\mathcal{A}}_{k+1}$. If all $H$ have size at least $n-r-k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. Otherwise a pair with $|G|\le t+k$ and $|H|\le n-r-k-1$ violates compatibility. HenceBoth candidates are available, so this proves the maximum formula also at the boundaries.

For completeness, their equality and the maximizing intervals follow from a direct count, with no appeal to the theorem. Moving from ${\mathcal{A}}_i$ to ${\mathcal{A}}_{i+1}$ adds sets containing both new coordinates and exactly $t+i-1$ old block points, and loses sets containing neither new coordinate and exactly $t+i$ old block points. ThusIn the nontrivial range, the gain-to-loss ratio is $\frac{(t+i)(r-t-i)}{(i+1)(n-r-i-1)}$. It exceeds, equals or falls below one according as $n$ is below, equal to or above $N_{i+1}$. Since the thresholds decrease with $i$ when $t>1$, the largest candidate is ${\mathcal{A}}_k$ in each strict interval and the consecutive candidates tie at $n=N_{k+1}$. This completes the proof of the cardinality theorem in every parameter range.

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.

The Kruskal-Katona theorem states that a colexicographic initial segment minimizes the lower shadow of a uniform set family of prescribed size. Its numerical form is as follows. For $m>0$, write the unique combinatorial number system expansionEvery $\mathcal{F}\subseteq [n{]}^{(r)}$ of size $m$ satisfiesThe empty family has empty lower shadow. Equality is attained by the first $m$ $r$-sets in colexicographic order, where the largest differing element belongs to the later set. Iterating the Kruskal-Katona theorem shows that the same colexicographic initial segment minimizes every iterated lower shadow.

For $1\le r<n/2$, the Erdős-Ko-Rado theorem givesfor an intersecting family $\mathcal{F}\subseteq [n{]}^{(r)}$. All $r$-sets containing one prescribed point show that the bound is sharp.

For the proof from the Kruskal-Katona theorem, put $k=n-r$ and form the complement family $\mathcal{G}=\{[n]\setminus A:A\in \mathcal{F}\}\subseteq [n{]}^{(k)}$. Let $\mathcal{S}$ be its rank-$r$ iterated lower shadow. No member $B\in \mathcal{F}$ belongs to $\mathcal{S}$: containment in $[n]\setminus A$ would give $A\cap B=\varnothing$, impossible for an intersecting family of nonempty sets. HenceSuppose $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The first $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ members of the colexicographic order are all $k$-sets of $[n-1]$. Their rank-$r$ iterated lower shadow is all $r$-sets of $[n-1]$, since $r<k$. The next $k$-set contains $n$ and has an $r$-subset containing $n$, so taking even one more member strictly enlarges that iterated lower shadow. By the iterated Kruskal-Katona theorem, $|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$. Together with $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this contradicts Pascal's identity and the preceding inequality. This proves the Erdős-Ko-Rado theorem.

For the Katona circle method proof, fix a cyclic ordering of $[n]$. A cyclic interval of length $r$ is specified by its final position. If no such interval belongs to $\mathcal{F}$, the bound below is automatic. Otherwise rotate one selected interval so that it ends at position $n$, and thus occupies positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Among the remaining endpoints, pair $j$ with $n-r+j$ for $1\le j\le r-1$. The corresponding intervals are disjoint when $n\ge 2r$, so at most one interval per pair is selected. Together with the interval ending at $n$, this gives the cyclic interval intersection bound of $r$ selected intervals.

Choose a uniformly random permutation and read its positions cyclically. A fixed $r$-set is a cyclic interval with probability $n/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$: each cyclic position gives a uniformly distributed $r$-set, and for $r<n$ the $n$ intervals are distinct. Summing over $\mathcal{F}$, the expected value of the number of selected intervals is $n|\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$. The cyclic interval intersection bound makes this at most $r$, giving $|\mathcal{F}|\le (r/n)\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$.

Finally apply the Katona circle method to an arbitrary antichain $\mathcal{A}$. If it contains $\varnothing$ or $[n]$, it has exactly one member and the LYM inequality holds with equality. Otherwise all its members have sizes $1,\dots ,n-1$. In a fixed cyclic ordering, the cyclic intervals sharing a final position form a nested chain as their lengths increase. At most one of them can belong to the antichain. Summing over the $n$ final positions proves the cyclic interval antichain bound of $n$ intervals. Taking the expected value over a uniformly random permutation givesAfter division by $n$, this is the LYM inequality proved by cyclic intervals. The case $n=0$ consists only of the empty set and is immediate.

Form the family $\mathcal{F}=\{A\subseteq [n]:{\sum }_{i\in A}{c}_i>1/2\}$. The nonnegative weights make it an up-set. It is an intersecting family, since two disjoint members would have combined weight exceeding one. The no-tie hypothesis makes it a self-dual set family: exactly one of $A,A^c$ belongs.

Let $a_j=|\mathcal{F}\cap (\genfrac{}{}{0ex}{}{[n]}{j})|/(\genfrac{}{}{0ex}{}{n}{j})$. Self-duality gives $a_{n-j}=1-a_j$. The Erdős-Ko-Rado theorem gives $a_j\le j/n$ for $j<n/2$; at $j=0$ this is immediate. If $n$ is even, $a_{n/2}=1/2$.

The biased measure of a set family is ${\mu }_p(\mathcal{F})={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)a_j{p}^j(1-p{)}^{n-j}$. By independence of the Bernoulli random variables, it equals $\mathbb{P}(Z\ge 1/2)$, since equality is excluded. Subtract $p={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)(j/n)p^j(1-p{)}^{n-j}$ and pair complementary levels. The complementary-layer bound for biased measure givesBoth factors are nonnegative for $p\ge 1/2$. The endpoints $p=1/2,1$ also follow directly, or by continuity. Thus the weighted Bernoulli majority bound is

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, an intersecting family $\mathcal{F}$ of $r$-subsets of $[n]$ satisfiesThe bound is sharp: take all $r$-sets containing one fixed element.

Use the Katona circle method. In any cyclic ordering of $[n]$, the cyclic interval intersection bound permits at most $r$ members of $\mathcal{F}$ to appear as length-$r$ intervals. To see the bound directly, rotate a chosen interval so that it ends at $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints except $n$ as $(j,j+n-r)$, $1\le j\le r-1$; the two intervals in each pair are disjoint, so at most one is chosen. Including the fixed interval gives at most $r$.

There are $(n-1)!$ oriented cyclic orders. A fixed $r$-set appears consecutively in $r!(n-r)!$ of them: collapse it to a block, cyclically order that block with the other $n-r$ elements, and order its members internally. Double counting the compatible family-member/order pairs gives $|\mathcal{F}|r!(n-r)!\le r(n-1)!$, proving the theorem.

We use the standard convention that a two-intersecting family satisfies $|A\cap B|\ge 2$ for every pair of members, including $A=B$. In particular every member has at least two elements.

An intersecting shadow lemma. If $\mathcal{F}$ is an intersecting family of $r$-sets, $r\ge 1$, thenHere is a proof, so no additional shadow theorem is being assumed. For $i<j$, an elementary set shift replaces a member $A$ containing $j$ but not $i$ by $(A\setminus \{j\})\cup \{i\}$ exactly when that replacement is not already in the family. This preserves cardinality and the intersecting family property. The only potentially troublesome pair consists of a moved member and an unmoved member $B$ containing $j$ but not $i$. But then $B$'s replacement was already present, and the two original members obtained by using that replacement would have been disjoint if the new pair were disjoint.

Alsoso an elementary set shift cannot increase the lower shadow. For completeness, a shadow set containing neither $i,j$ or both has an unchanged witness in the original lower shadow. A shadow set containing $i$ but not $j$ is either originally present or the replacement of an originally present shadow set. If a shadow set contains $j$ but not $i$, its witnessing member survived the elementary set shift; either that member contains both coordinates, or its replacement was already present. In either case both the shadow set and its replacement were originally present, so the former survives in the shifted lower shadow.

Repeated elementary set shifts terminate because the sum of the elements of all members decreases whenever the family changes. In the resulting shifted set family $\mathcal{H}$, if $a_1<\cdots <a_r$ is a member and $b_1<\cdots <b_r$ satisfies $b_i\le a_i$ for every $i$, then $\{b_1,\dots ,b_r\}$ is also a member. Every $A\in \mathcal{H}$ has a prefix $[2q-1]$ containing $q$ of its elements. Otherwise its sorted elements satisfy $a_i\ge 2i$, and the first $r$ elements outside $A$ form a disjoint member componentwise no larger than $A$, contradicting the intersecting family property.

Choose the first such prefix and reflect membership inside it:This has size $r-1$. The set $D\cup \{2q-1\}$ is componentwise no larger than $A$: before the first excess, the prefix counts of $A$ are at most half the prefix length, and reflection only moves selected positions to the left. Thus $D$ belongs to $\partial \mathcal{H}$. This ballot reflection injection is injective: in $D$, the reflected prefix ends at the first position where unselected positions outnumber selected ones, and reflecting it again recovers $A$. Consequently $|\partial \mathcal{H}|\ge |\mathcal{H}|=|\mathcal{F}|$. Since elementary set shifts did not increase the lower shadow, this proves the intersecting shadow lemma.

The nonuniform two-intersecting family bound. Write ${\mathcal{A}}_i=\mathcal{A}\cap [n{]}^{(i)}$. No member of $\partial {\mathcal{A}}_i$ can be the complement of a member of ${\mathcal{A}}_{n-i+1}$: such an inclusion would make the intersection of the two original members have at most one element. The intersecting shadow lemma therefore givesFor $n=2h$, sum this over $1\le i\le h$. These pairs cover all nonempty levels, soEquality is attained by all subsets of size at least $h+1$: any two intersect in at least two elements.

For $n=2h+1$, the same pairs cover every level except $h+1$. Complements of the members of ${\mathcal{A}}_{h+1}$ form an intersecting family of $h$-sets, sinceFor $h\ge 1$, the permitted Erdős-Ko-Rado theorem bounds this middle level by $\left(\genfrac{}{}{0ex}{}{2h}{h-1}\right)=\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)$. HenceEquality is attained by all $(h+1)$-sets inside $[2h]$, together with all subsets of $[2h+1]$ of size at least $h+2$. Two members of the first group intersect in at least two elements; a member from each group intersects in at least two; two members of the second group intersect in at least three. For $n=1$ the only two-intersecting family is empty, which also gives equality. The empty-ground-set case is likewise immediate.

The pair-cover bound for a two-intersecting uniform family. If $\mathcal{A}$ is nonempty, fix $A_0\in \mathcal{A}$, with $|A_0|=r$. Every member contains one of the $\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ pairs inside $A_0$. Each fixed pair belongs to exactly $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets, so counting their union givesThe empty family is immediate; a nonempty two-intersecting family requires $r\ge 2$.

Witness-pair concentration for an intersecting uniform family. Let $\mathcal{A}$ now be an intersecting family of $r$-sets. If it is two-intersecting, the preceding bound, together with $\left(\genfrac{}{}{0ex}{}{r}{2}\right)\le (r-1{)}^2$ for $r\ge 2$, shows that any chosen $x\in [n]$ has the required property. Otherwise there are members $A,B$ with $A\cap B=\{x\}$. Every member $C$ not containing $x$ must contain some $a\in A\setminus \{x\}$ and some $b\in B\setminus \{x\}$. These two sets of possible witnesses are disjoint. There are $(r-1{)}^2$ witness pairs, and each is contained in $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets. ThusFor $r=1$, a nonempty intersecting family consists of one singleton; choose its element and the number avoiding it is zero. This is the natural separate interpretation of the degenerate case, where the printed binomial coefficient has lower index $-1$. For an empty family any $x\in [n]$ works, provided $n\ge 1$ as usual.

Use the identification of two-element subsets of $[n]$ with the edges of the complete graph $K_n$. A colour class in the Kneser graph $KG(n,2)$ is an intersecting two-element set family, so its edges must pairwise meet.

Such a class is contained either in a star graph or in a triangle in a graph. Indeed, if not all edges have a common vertex, take two meeting edges $ab,ac$. An edge not containing $a$ must then be $bc$. Any further edge meeting all three of $ab,ac,bc$ is one of these three. Classes with at most two edges already lie in a star graph.

Assume that a graph colouring used $c\le n-3$ colours. Classify $s$ classes as stars and the remaining $t=c-s$ classes as triangles. Delete a chosen centre of each star class, leaving $m\ge n-s\ge t+3$ vertices. Every edge between those remaining vertices must belong to a triangle class, of which each covers at most three edges. HenceButa contradiction. Thus $\chi (KG(n,2))\ge n-2$. For the matching upper bound, assign a two-set the colour of its smaller element if that element is at most $n-3$, and otherwise give it colour $n-2$. The last class comprises the three pairs on the last three elements, an intersecting family. Consequently an entirely combinatorial argument gives

The Kneser graph $KG(n,k)$ has the $k$-element subsets of $[n]$ as its vertices; two vertices are adjacent exactly when the corresponding subsets are disjoint. The Lovász theorem on Kneser graphs determines its chromatic number. A graph colouring is therefore a partition of the $k$-sets into intersecting families.

First construct a graph colouring with $d+2=n-2k+2$ colours. If a $k$-set meets $[d+1]$, give it the colour of its least element. Give every remaining $k$-set colour $d+2$. Two sets with one of the first $d+1$ colours share that colour's element. The last colour consists of $k$-sets in a $(2k-1)$-element ground set, so it too is an intersecting family. Thus $\chi (KG(n,k))\le d+2$.

For the converse we establish the Gale hemisphere lemma explicitly, using a signed moment curve. Choose $t_1<\cdots <t_n$ and putEvery open hemisphere $\{v:x\cdot v>0\}$ contains at least $k$ labelled points $v_i$. To see this, put $p(t)=x_0+x_{1}t+\cdots +x_d{t}^d$. It is a nonzero polynomial of polynomial degree at most $d$. First suppose none of the $p(t_i)$ vanishes. Write $b_i=\mathrm{sgn}((-1{)}^{i}p(t_i))$. If only $P\le k-1$ of the $b_i$ were positive, the $N=n-P$ negative signs would occupy at most $P+1$ consecutive blocks. There would be at leastadjacent pairs with both $b_i,b_{i+1}$ negative. Each such pair forces $p(t_i)$ and $p(t_{i+1})$ to have opposite signs. The intermediate value theorem would give $d+1$ distinct roots of a polynomial, a contradiction.

If $p$ vanishes at $z$ of the sample points, then $z\le d$. A Lagrange interpolation polynomial $q$ of polynomial degree at most $z-1$ can be chosen with $(-1{)}^{i}q(t_i)<0$ at all those points. For sufficiently small $\epsilon >0$, the polynomial $p+\epsilon q$ keeps every previously nonzero sign, has no zero sample values, and makes every previously zero value negative after multiplication by $(-1{)}^i$. Its positive count is exactly the positive count of $p$, so the preceding argument proves the open hemisphere assertion also in this case. For $d=0$, the labelled points alternate between the two points of $S^0$; distinct labels, rather than distinct positions, are what is needed.

Suppose now that $KG(n,k)$ had a graph colouring with at most $d+1$ colours, padding the palette with unused colours if necessary. For each colour $j$, letThese are open sets, and the Gale hemisphere lemma says that they cover $S^d$. If both $x$ and $-x$ belonged to $U_j$, two $k$-sets of colour $j$ would lie in opposite open hemispheres. They would be disjoint, hence adjacent in the Kneser graph, contradicting the graph colouring. The Lusternik-Schnirelmann-Borsuk theorem excludes this cover. Therefore the lower bound matches the explicit colouring: