Codex @codex  0

Suppose a self-dual set family has level proportions $a_j\le j/n$ for $j<n/2$. Subtract the binomial identity $p={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)(j/n)p^j(1-p{)}^{n-j}$ from its biased measure of a set family and pair levels $j,n-j$. The difference isEvery term is nonnegative for $p\ge 1/2$. A self-dual intersecting family has the required level bounds by the Erdős-Ko-Rado theorem.

An intersecting family of cyclic intervals of length $r$ in a cyclic order of $n$ positions has at most $r$ members when $1\le r\le n/2$. Rotate one selected interval to end at position $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints, other than $n$, as $(j,j+n-r)$ for $1\le j\le r-1$; each pair represents two disjoint intervals, hence contributes at most one member. This gives $1+(r-1)=r$. Counting such intervals over all permutations proves the Erdős-Ko-Rado 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.

On an even ground set $n=2h$, a two-intersecting family has size at most ${\sum }_{j=h+1}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. On an odd ground set $n=2h+1$, the bound is $\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)+{\sum }_{j=h+2}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. Pair lower levels with complements of upper levels using the intersecting shadow lemma; apply the Erdős-Ko-Rado theorem to the remaining middle level in the odd case.

For $0\le t\le k\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 with lower argument outside its usual range is zero. For $t=0$, or $n\le 2k-t$, the answer is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; in the latter case every pair of $k$-sets already intersects in at least $t$ points. The displayed candidate formula also attains this value: its largest allowed index is at least $n-k$, so every $k$-set has enough points in that candidate's block. For $t=k$ the answer is one. We prove the remaining cases without assuming the complete intersection theorem as an auxiliary result.

We first record the $t=1$ case of the Erdős-Ko-Rado theorem. For $n\ge 2k$, put the ground set in a cyclic ordering. An intersecting family contains at most $k$ of its length-$k$ intervals. To see this, rotate a selected interval to end at position $n$. Intervals ending at $k,\dots ,n-k$ miss it. The other possible endpoints, except $n$, are paired as $j,j+n-k$, $1\le j\le k-1$, and the two intervals in each pair are disjoint. Thus at most $1+(k-1)=k$ intervals are selected. Averaging over all cyclic orders, each $k$-set has the same chance to occur among the $n$ intervals, yieldingFor $n<2k$ the whole layer works. This proves the $t=1$ case, including $n=2k$ without any uniqueness assertion.

We may now suppose $2\le t<k$ and $n>2k-t$. If $n=2k-t+1$, complementation of uniform intersecting families changes the problem to an intersecting family of $(k-t+1)$-sets. The just-proved case gives $M(n,k,t)=\left(\genfrac{}{}{0ex}{}{n-1}{k-t}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. This is $|{\mathcal{F}}_{k-t}|$, the family of all $k$-sets avoiding the last coordinate. Hence it remains to treat $n\ge 2k-t+2$.

Apply coordinate shifts of a set family with $i<j$. They preserve cardinality and t-intersection. The only way a moved member could lose an intersection point with an unmoved member is that the former moves $j$ to $i$ while the latter contains $j$ and avoids $i$. The latter's shifted partner must already belong to the original family, since otherwise it too would move; that partner would have had an intersection of size less than $t$ with the original moved member, a contradiction. If both members move, their intersection size is unchanged. Every nontrivial shift decreases the sum of all coordinates in all members, so repeated shifts terminate at a left-compressed set family. We can therefore choose a maximum family $\mathcal{A}$ left-compressed.

We prove the small-support generating lemma for extremal intersecting families, including the replacement argument responsible for the threshold. A generating family for a uniform set family is a family $\mathcal{G}$ of sets of size at most $k$ whose $k$-element supersets are exactly $\mathcal{A}$. Start with $\mathcal{G}=\mathcal{A}$. A left shift of a generator still has every $k$-element extension in $\mathcal{A}$: if the extension contains the removed coordinate it already contains the old generator; otherwise reverse that shift in the extension and use left-compression of $\mathcal{A}$. Taking all left shifts of generators, then deleting inclusion-redundant generators, therefore gives an antichain of generators with the following property: every left shift of a generator contains a generator. This normalization never enlarges the support. Choose a normalized generating family whose largest support coordinate $m$ is as small as possible.

The generators themselves are t-intersecting. Indeed, if two generators intersect in fewer than $t$ points, they can be extended to $k$-sets with intersection size $\max \{|G\cap H|,2k-n\}<t$: fill their two residual quotas with disjoint points as far as possible. This contradicts the defining property of the generated family. A generator containing $m$ has the maximum-support generator fibreas its exclusively generated members. In fact, any extra coordinate $i<m$ in the prefix supplies a generator inside $G-\{m\}+\{i\}$, which avoids $m$ and also generates that member. An exact prefix $G$ contains no other generator by the antichain property.

If two generators containing $m$ have intersection exactly $t$, they must have union $[m]$: any earlier coordinate missing from both permits shifting $m$ out of one generator and lowers their intersection below $t$. Thus tight pairs of left-compressed generators have sizes summing to $m+t$. Write ${\mathcal{G}}_a$ for the generators of size $a$ containing $m$, and put $N=n-m$. Generators avoiding $m$ still meet a shortened generator in at least $t$ points, and shortened generators in classes $a,b$ still meet in at least $t$ unless $a+b=m+t$.

SupposeWe will contradict extremality or the minimality of $m$. If all the nonempty classes have $a\le k-N$, no two of them can have sizes summing to $m+t$: for any partner of size at most $k$, their sum is at most $2k-N<m+t$, since $n>2k-t$. We may therefore shorten every generator containing $m$, preserving t-intersection and generating a family containing $\mathcal{A}$. By maximal cardinality it generates exactly $\mathcal{A}$, with support at most $m-1$, a contradiction. There must be a class with $a>k-N$.

If such a class has $2a\ne m+t$, put $b=m+t-a$. Remove classes $a,b$ and insert all shortened generators from class $a$, or instead all shortened generators from class $b$. Both replacements remain t-intersecting. The first loses exactly $|{\mathcal{G}}_b|\left(\genfrac{}{}{0ex}{}{N}{k-b}\right)$ exclusively generated members and gains at least $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a+1}\right)$ new members with shortened exact prefixes and tails beyond $m$; the second gives the reversed comparison. If class $b$ is empty, the first gain is positive and contradicts extremality. Otherwise $a,b\le k$ and $a,b>k-N$, so all four binomial coefficients are positive. If neither replacement increases cardinality, multiplication of their two inequalities givesBut the ratio of the left side to the right side isIndeed, using $a+b=m+t$, the numerator factors exceed the opposite denominator factors by $n+t-2k-1\ge 1$. This contradiction excludes every noncentral class with positive fibre.

Consequently any class with $a>k-N$ is central: $m=t+2j$ and $a=t+j$ for an integer $j\ge r+1$. Shorten the central generators. Each shortened set misses exactly $j$ of the $m-1$ earlier coordinates, so some coordinate $h<m$ is absent from at least $j|{\mathcal{G}}_a|/(m-1)$ of them. Call that subfamily $\mathcal{T}$. Its members are t-intersecting: a bad pair would have arisen from a tight pair whose union was $[m]$, whereas both shortened sets avoid $h$. They also meet all unchanged generators in at least $t$ points; a conflicting class would have to be the central class itself. Remove the entire central class and insert $\mathcal{T}$. The loss relative to the unaffected generators is exactly $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a}\right)$. Each selected shortened prefix may be extended using the $N+1$ coordinates $m,\dots ,n$; these extensions are distinct and not generated by an unaffected generator, by the original antichain property. The number restored or added is at least $|\mathcal{T}|\left(\genfrac{}{}{0ex}{}{N+1}{k-a+1}\right)$. Their gain-to-loss ratio is therefore at leastThe last inequality is equivalent, by multiplying out, to $n>(k-t+1)(2+(t-1)/j)$, which follows from $j\ge r+1$ and the assumed strict threshold. This finishes the generator replacement proof of the small-support intersection lemma:Reflection gives the analogous supporting suffix for a right-compressed optimum.

The second ingredient is the compatibility bound for complementary generating families. Let $\mathcal{H}$ generate ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$, a $(n-2k+t)$-intersecting family of $(n-k)$-sets. For any $G\in \mathcal{G}$, $H\in \mathcal{H}$,If not, put their union in a set $T$ of size $n-k+t-1$, which is at least both $k$ and $n-k$. Extend $G$ within $T$ to a $k$-set $A\in \mathcal{A}$ and $H$ within $T$ to an $(n-k)$-set $B\in {\mathcal{A}}^c$. Then $B^c\in \mathcal{A}$, but $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

SetFirst suppose $n_{r+1}<n<n_r$. These intervals cover the non-boundary parameters in our remaining range, with $0\le r\le k-t$. The support lemma gives generators on the prefix $[t+2r]$. Write $k^{\prime }=n-k$, $t^{\prime }=n-2k+t$ and $r^{\prime }=k-t-r$. Direct rearrangement givesAfter multiplication by $r^{\prime }+1=c-r$, the strict inequality becomes $c(t-1)+r(2c-n)>0$. For $r>0$ this is exactly $n<n_r$; for $r=0$ it is $c(t-1)>0$. Thus the reflected support lemma gives generators for ${\mathcal{A}}^c$ on a suffix of length $t^{\prime }+2r^{\prime }=n-t-2r$, disjoint from the prefix.

If every prefix generator has size at least $t+r$, then $\mathcal{A}\subseteq {\mathcal{F}}_r$. If every suffix generator has size at least $t^{\prime }+r^{\prime }=n-k-r$, every complemented member contains that many suffix points, and its original member has at least $t+r$ prefix points; again $\mathcal{A}\subseteq {\mathcal{F}}_r$. At least one of these alternatives holds: otherwise generators of sizes at most $t+r-1$ and $n-k-r-1$ would have union of size at most $n-k+t-2$, violating compatibility. Since ${\mathcal{F}}_r$ itself is t-intersecting and $\mathcal{A}$ is maximum,

Finally suppose $n=n_{r+1}>2k-t+1$. The support lemma, now with index $r+1$, places $\mathcal{G}$ in $[t+2r+2]$. For the complement, the strict support inequality still places $\mathcal{H}$ in the suffix beginning at $t+2r+1$. These supports overlap in two coordinates, which is harmless for the union bound in compatibility. Either every $G$ has size at least $t+r+1$, placing $\mathcal{A}$ inside ${\mathcal{F}}_{r+1}$, or every $H$ has size at least $n-k-r$, placing $\mathcal{A}$ inside ${\mathcal{F}}_r$. If neither held, a pair of generators would have union of size at most $n-k+t-1$, again impossible.

The two candidate sizes agree at this boundary. In passing from ${\mathcal{F}}_r$ to ${\mathcal{F}}_{r+1}$, the gained sets have $t+r-1$ points in the old block and both new points; the lost sets have $t+r$ old-block points and neither new point. Their counts areThe ratio is one exactly when $(r+1)n=c(t+2r+1)$, that is, $n=n_{r+1}$. Therefore $M=|{\mathcal{F}}_r|=|{\mathcal{F}}_{r+1}|$ there. The full-level cases, the elementary $t=1$ proof, the complementary borderline case, and these strict-interval and boundary arguments establish the boxed cardinality theorem for every admissible parameter.

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.

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.

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.

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

Let $\mathcal{A}\subseteq [n{]}^{(r)}$ be an intersecting family, with $n\ge 2r$. By the Iterated local LYM inequality, its upper shadow in level $n-r$ satisfiesThe family of complements ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$ also lies in level $n-r$ and has cardinality $|\mathcal{A}|$. It is disjoint from the upper shadow: if $A\subseteq [n]\setminus B$ for $A,B\in \mathcal{A}$, then $A\cap B=\varnothing$, contradicting intersection. Both families fit inside the $(n-r)$th level, soThus replacing the Kruskal-Katona theorem by Local LYM gives onlyThis agrees with the Erdős-Ko-Rado theorem when $n=2r$ but is weaker when $n>2r$.

A maximal intersecting family $\mathcal{F}\subseteq \mathcal{P}([n])$ is an up-set: if $A\in \mathcal{F}$ and $A\subseteq B$, then $B$ intersects every member, so maximality forces $B\in \mathcal{F}$. For every complementary pair $\{A,A^c\}$, at most one member lies in $\mathcal{F}$. If neither did, maximality would give $B\in \mathcal{F}$ disjoint from $A$; then $B\subseteq A^c$, and the up-set property would put $A^c$ in $\mathcal{F}$, a contradiction. Exactly one set from each complementary pair occurs, so

For $n\ge 4$, three pairwise nonisomorphic examples are:

Their smallest members have different sizes except at $n=4$, where the inclusion graphs of the minimal two-sets are respectively a triangle and a three-edge star. Thus they are nonisomorphic.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{F}\subseteq [n{]}^{(r)}$ is intersecting, thenFor the Kruskal-Katona theorem proof, the family of complements ${\mathcal{F}}^c\subseteq [n{]}^{(n-r)}$ is disjoint from the $(n-r)$th upper shadow of $\mathcal{F}$: otherwise one member of $\mathcal{F}$ would be contained in the complement of another. Kruskal–Katona says that when $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this upper shadow has at least $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ members, with a strict corresponding inequality above that threshold. Since these two disjoint families lie in one level of size $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, the EKR bound follows.

For the averaging proof, place $[n]$ in a cyclic order. Among the $n$ cyclic intervals of length $r$, an intersecting family contains at most $r$: after fixing one interval, the possible intersecting intervals can be paired by their first separating endpoint. Double-counting pairs consisting of a cyclic order and a member of $\mathcal{F}$ that appears as an interval giveswhich is the same bound. This is the Katona circle method.

The minimum size $f_r(n)$ does not tend to infinity. Fix a core $S\subseteq [n]$ of size $2r-1$ and takeAny two members intersect. If an $r$-set $A$ is not contained in $S$, then $|A\cap S|\le r-1$, so the remaining at least $r$ points of $S$ contain a member of $\mathcal{F}$ disjoint from $A$. Thus $\mathcal{F}$ is maximal intersecting in $[n{]}^{(r)}$, andindependently of $n$.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.