Get Kruskal%E2%80%93Katona Theorem essential facts below. View Videos or join the Kruskal%E2%80%93Katona Theorem discussion. Add Kruskal%E2%80%93Katona Theorem to your PopFlock.com topic list for future reference or share this resource on social media.
About the numbers of faces of different dimensions in an abstract simplicial complex
Given two positive integers N and i, there is a unique way to expand N as a sum of binomial coefficients as follows:
This expansion can be constructed by applying the greedy algorithm: set ni to be the maximal n such that replace N with the difference, i with i - 1, and repeat until the difference becomes zero. Define
Statement for simplicial complexes
An integral vector is the f-vector of some -dimensional simplicial complex if and only if
Statement for uniform hypergraphs
Let A be a set consisting of N distinct i-element subsets of a fixed set U ("the universe") and B be the set of all -element subsets of the sets in A. Expand N as above. Then the cardinality of B is bounded below as follows:
Lovász' simplified formulation
The following weaker but useful form is due to László Lovász (1993) Let A be a set of i-element subsets of a fixed set U ("the universe") and B be the set of all -element subsets of the sets in A. If then .
In this formulation, x need not be an integer. The value of the binomial expression is .
Given a vector with positive integer components, let ?f be the subset of the power set 2N consisting of the empty set together with the first i-element subsets of N in the list for i = 1, ..., d. Then the following conditions are equivalent:
Vector f is the f-vector of a simplicial complex ?.