Set family shadow

A shadow moves a uniform set family to an adjacent level of the subset lattice by deleting or adding one element.

Lower shadow ( $\partial A$ )

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

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

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

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

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

Among families of fixed size, an initial lexicographic segment minimizes its upper shadow.

There are no discussions about this article yet.

There are currently no matching articles.