Lower shadow ( $\partial A$ )

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

\partial A = {B \in [n]^{(r - 1)} : B \subset A for some A \in A} .

Kruskal-Katona theorem

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

then

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

Let

f_{r} (m)

be the lower-shadow size prescribed by the binomial representation in the Kruskal-Katona theorem. Then

f_{r} (a + b) \leq max {f_{r} (a), b} + f_{r - 1} (b) .

Induction using Pascal's identity proves the inequality and drives the standard ground-set induction for the theorem.

There are no discussions about this article yet.

There are currently no matching articles.