Kruskal–Katona theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. It can be used to derive facts about abstract simplicial complexes. It is named for Joseph Kruskal and Gyula Katona.

For an n-element set X, define the shadow \partial X as the family of (n − 1)-element subsets of X, and for a family A of n-element subsets of a universe U (i.e., an n-hypergraph), define the shadow as the union of the shadows of the constituent sets,

\partial A = \bigcup \{ \partial X \mid X \in A \}.

The Kruskal–Katona theorem states that the size of \partial A is minimized when A consists of the | A | lexicographically first subsets of U. Denoting m = | A | , we can write m in the form

m = {m_t \choose t} + {m_{t-1} \choose t-1} + ... + {m_{u} \choose u},

where m_t>m_{t-1}>\dots>m_{u}\ge u\ge 1, and thus

|\partial A| \ge {m_t \choose t-1} + {m_{t-1} \choose t-2} + ... + {m_{u} \choose u-1},

with equality if (but not, in general, only if) A consists of the m lexicographically first subsets of U. Symmetrically, if we define the upward shadow \partial_u X as the family of (n + 1)-element supersets of X, we have that |\partial_u A| is minimal when A consists of the m lexicographically last subsets of U.

The theorem was discovered in

  • J.B. Kruskal: The number of simplices in a complex, Mathematical Optimization Techniques, R. Bellman (ed.), University of California Press, 1963.
  • G.O.H. Katona: A theorem of finite sets, Theory of Graphs, P. Erdős and G. Katona (eds.), Akadémiai Kiadó and Academic Press, 1968.

For a proof via a more general theorem in discrete geometry, see

Retrieved from "http://en.wikipedia.org../../../k/r/u/Kruskal%E2%80%93Katona_theorem_9745.html"