Kruskal–Katona theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the f-vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform hypergraphs. The theorem is named after Joseph Kruskal and Gyula O. H. Katona. It was independently proved by Marcel Schützenberger, but his contribution escaped notice for several years.

Statement[edit]

Given two positive integers N and i, there is a unique way to expand N as a sum of binomial coefficients as follows:

 N=\binom{n_i}{i}+\binom{n_{i-1}}{i-1}+\ldots+\binom{n_j}{j},\quad
n_i > n_{i-1} > \ldots > n_j \geq j\geq 1.

This expansion can be constructed by applying the greedy algorithm: set ni to be the maximal n such that  N\geq \binom{n}{i}, replace N with the difference, i with i − 1, and repeat until the difference becomes zero. Define

 N^{(i)}=\binom{n_i}{i+1}+\binom{n_{i-1}}{i}+\ldots+\binom{n_j}{j+1}.

Statement for simplicial complexes[edit]

An integral vector (f_0, f_1, ..., f_{d-1}) is the f-vector of some (d-1)-dimensional simplicial complex if and only if

 0 \leq f_{i} \leq f_{i-1}^{(i)},\quad 1\leq i\leq d-1.

Statement for uniform hypergraphs[edit]

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 (i-r)-element subsets of the sets in A. Expand N as above. Then the cardinality of B is bounded below as follows:

 |B| \geq  \binom{n_i}{i-r}+\binom{n_{i-1}}{i-r-1}+\ldots+\binom{n_j}{j-r}.

Ingredients of the proof[edit]

For every positive i, list all i-element subsets a1 < a2 < … ai of the set N of natural numbers in the reverse lexicographic order. For example, for i = 3, the list begins

 123, 124, 134, 234, 125, 135, 235, 145, 245, 345, \ldots.

Given a vector f = (f_0, f_1, ..., f_{d-1}) with positive integer components, let Δf be the subset of the power set 2N consisting of the empty set together with the first f_{i-1} i-element subsets of N in the list for i = 1, …, d. Then the following conditions are equivalent:

  1. Vector f is the f-vector of a simplicial complex Δ.
  2. Δf is a simplicial complex.
  3.  f_{i} \leq f_{i-1}^{(i)},\quad 1\leq i\leq d-1.

The difficult implication is 1 ⇒ 2.

See also[edit]

References[edit]

  • Kruskal, J. B. (1963), "The number of simplices in a complex", in Bellman, R., Mathematical Optimization Techniques, University of California Press .

External links[edit]