Solution

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 expansion

m = (r a _{r}) + (r - 1 a _{r - 1}) + \dots + (s a _{s}), a_{r} > a_{r - 1} > \dots > a_{s} \geq s \geq 1.

(1)

Every

F \subseteq [n]^{(r)}

of size

m

satisfies

∣ \partial F ∣ \geq (r - 1 a _{r}) + (r - 2 a _{r - 1}) + \dots + (s - 1 a _{s}) .

(2)

The 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 \leq r < n /2

, the Erdős-Ko-Rado theorem gives

∣ F ∣ \leq (r - 1 n - 1)

(3)

for an intersecting family

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

G = {[n] ∖ A : A \in F} \subseteq [n]^{(k)}

. Let

S

be its rank-

r

iterated lower shadow. No member

B \in F

belongs to

S

: containment in

[n] ∖ A

would give

A \cap B = \emptyset

, impossible for an intersecting family of nonempty sets. Hence

∣ F ∣ + ∣ S ∣ \leq (r n) .

(4)

Suppose

∣ F ∣ > (r - 1 n - 1) = (k n - 1)

. The first

(k n - 1)

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,

∣ S ∣ > (r n - 1)

. Together with

∣ F ∣ > (r - 1 n - 1)

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

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 \leq j \leq r - 1

. The corresponding intervals are disjoint when

n \geq 2 r

, 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 / (r n)

: each cyclic position gives a uniformly distributed

r

-set, and for

r < n

the

n

intervals are distinct. Summing over

F

, the expected value of the number of selected intervals is

n ∣ F ∣/ (r n)

. The cyclic interval intersection bound makes this at most

r

, giving

∣ F ∣ \leq (r / n) (r n) = (r - 1 n - 1)

Finally apply the Katona circle method to an arbitrary antichain

A

. If it contains

\emptyset

[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