Namespaces
Variants
Actions

Difference between revisions of "Kruskal-Katona theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: expand bibliodata)
m (gt to >)
 
(2 intermediate revisions by one other user not shown)
Line 7: Line 7:
  
 
{{TEX|semi-auto}}{{TEX|done}}
 
{{TEX|semi-auto}}{{TEX|done}}
Let $[ n ] : = \{ 1 , \dots , n \}$ and $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \}$, $k = 0 , \dots , n$ (cf. also [[Sperner property|Sperner property]]; [[Sperner theorem|Sperner theorem]]). The elements of $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ can be linearly ordered in the following way: $X < Y$ if the largest element in which $X$ and $Y$ differ is in $Y$ (cf. also [[Totally ordered set|Totally ordered set]]). If $\{ a _ { 1 } + 1 , \dots , a _ { k } + 1 \}$, $0 \leq a _ { 1 } < \ldots < a _ { k } \leq n - 1$, is the $( m + 1 )$th element in this order, then
+
Let $[ n ] : = \{ 1 , \dots , n \}$ and $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \}$, $k = 0 , \dots , n$ (cf. also [[Sperner property|Sperner property]]; [[Sperner theorem|Sperner theorem]]). The elements of $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ can be linearly ordered in the following way: $X < Y$ if the largest element in which $X$ and $Y$ differ is in $Y$ (cf. also [[Totally ordered set|Totally ordered set]]). If $\{ a _ { 1 } + 1 , \dots , a _ { k } + 1 \}$, $0 \leq a _ { 1 } < \ldots < a _ { k } \leq n - 1$, is the $( m + 1 )$th element in this order, then
  
 
\begin{equation} \tag{a1} m = \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) + \left( \begin{array} { c } { a _ { k  - 1} } \\ { k - 1 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 2 } } \\ { 2 } \end{array} \right) + \left( \begin{array} { c } { a _ { 1 } } \\ { 1 } \end{array} \right), \end{equation}
 
\begin{equation} \tag{a1} m = \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) + \left( \begin{array} { c } { a _ { k  - 1} } \\ { k - 1 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 2 } } \\ { 2 } \end{array} \right) + \left( \begin{array} { c } { a _ { 1 } } \\ { 1 } \end{array} \right), \end{equation}
Line 23: Line 23:
 
The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if $\mathcal{F}$ is any $m$-element family in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $m$ is given by (a1), then
 
The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if $\mathcal{F}$ is any $m$-element family in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $m$ is given by (a1), then
  
\begin{equation*} \Delta ( {\cal F} ) | \geq \partial _ { k } ( m ). \end{equation*}
+
\begin{equation*} | \Delta ( {\cal F} ) | \geq \partial _ { k } ( m ). \end{equation*}
  
 
There exist generalizations to similar results for other partially ordered sets, like products of chains, products of stars, the partially ordered set of subwords of $0$-$1$-words, and the partially ordered set of submatrices of a matrix.
 
There exist generalizations to similar results for other partially ordered sets, like products of chains, products of stars, the partially ordered set of subwords of $0$-$1$-words, and the partially ordered set of submatrices of a matrix.
Line 37: Line 37:
 
====References====
 
====References====
 
<table>
 
<table>
<tr><td valign="top">[a1]</td> <td valign="top">  K. Engel,  "Sperner theory" , Encyclopedia of Mathematics and its Applications '''65''', Cambridge Univ. Press  (1997) ISBN 0-521-45206-6 {{ZBL|0868.05001}}</td></tr>
+
<tr><td valign="top">[a1]</td> <td valign="top">  K. Engel,  "Sperner theory" , Encyclopedia of Mathematics and its Applications '''65''', Cambridge Univ. Press  (1997) {{ISBN|0-521-45206-6}} {{ZBL|0868.05001}}</td></tr>
 
<tr><td valign="top">[a2]</td> <td valign="top">  P. Frankl,  "Extremal set systems"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , '''2''' , Elsevier  (1995)  pp. 1293–1329</td></tr>
 
<tr><td valign="top">[a2]</td> <td valign="top">  P. Frankl,  "Extremal set systems"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , '''2''' , Elsevier  (1995)  pp. 1293–1329</td></tr>
 
<tr><td valign="top">[a3]</td> <td valign="top">  J.B. Kruskal,  "The number of simplices in a complex" , ''Mathematical Optimization Techniques'' , Univ. California Press  (1963)  pp. 251–278. {{ZBL|0116.35102}}</td></tr>
 
<tr><td valign="top">[a3]</td> <td valign="top">  J.B. Kruskal,  "The number of simplices in a complex" , ''Mathematical Optimization Techniques'' , Univ. California Press  (1963)  pp. 251–278. {{ZBL|0116.35102}}</td></tr>
<tr><td valign="top">[a4]</td> <td valign="top">  G.O.H. Katona,  "A theorem of finite sets" , ''Theory of Graphs. Proc. Colloq. Tihany'' , Akad. Kiadó  (1966)  pp. 187–207</td></tr>
+
<tr><td valign="top">[a4]</td> <td valign="top">  G.O.H. Katona,  "A theorem of finite sets" , ''Theory of Graphs. Proc. Colloq. Tihany'' , Akad. Kiadó  (1966)  pp. 187–207. {{ZBL|0313.05003}} {{ZBL|0612.05001}}</td></tr>
 
</table>
 
</table>

Latest revision as of 14:52, 11 November 2023

Let $[ n ] : = \{ 1 , \dots , n \}$ and $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \}$, $k = 0 , \dots , n$ (cf. also Sperner property; Sperner theorem). The elements of $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ can be linearly ordered in the following way: $X < Y$ if the largest element in which $X$ and $Y$ differ is in $Y$ (cf. also Totally ordered set). If $\{ a _ { 1 } + 1 , \dots , a _ { k } + 1 \}$, $0 \leq a _ { 1 } < \ldots < a _ { k } \leq n - 1$, is the $( m + 1 )$th element in this order, then

\begin{equation} \tag{a1} m = \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) + \left( \begin{array} { c } { a _ { k - 1} } \\ { k - 1 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 2 } } \\ { 2 } \end{array} \right) + \left( \begin{array} { c } { a _ { 1 } } \\ { 1 } \end{array} \right), \end{equation}

since $\left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right)$ $k$-element subsets of $[ n ]$ have maximal element smaller than $a _ { k } + 1$, $\left( \begin{array} { c } { a _ { k - 1 } } \\ { k - 1 } \end{array} \right)$ have maximal element $a _ { k } + 1$ but the second largest element smaller than $a _ { k - 1} + 1$, etc.. Equation (a1) is called the $k$-representation of $m$, $1 \leq m \leq \left( \begin{array} { l } { n } \\ { k } \end{array} \right)$ (for $m = \left( \begin{array} { l } { n } \\ { k } \end{array} \right)$, one takes $a _ { 1 } = 0$, $a _ { 2 } = 1 , \dots , a _ { k - 1 } = k - 2$, $a _ { k } = n$). This (unique) representation can be found directly by choosing $a_k$ maximal such that $\left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right) \leq m$, $a_{k - 1}$ maximal such that $\left( \begin{array} { c } { a _ { k - 1 } } \\ { k - 1 } \end{array} \right) \leq m - \left( \begin{array} { c } { a _ { k } } \\ { k } \end{array} \right)$, etc..

For a family ${\cal F} \subseteq \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$, the lower shadow of $\mathcal{F}$ is defined by

\begin{equation*} \Delta ( \mathcal{F} ) : = \left\{ Y \in \left( \begin{array} { c } { [ n ] } \\ { k - 1 } \end{array} \right) : Y \subset X \text { for some } X \in \mathcal{F} \right\}. \end{equation*}

If $m$ is given as above, then the lower shadow of the family of the first $m$ elements in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ is the family of all $( k - 1 )$-element subsets of $[ n ]$ having maximal element smaller than $a _ { k } + 1$, of all $( k - 1 )$-element subsets of $[ n ]$ having maximal element $a _ { k } + 1$, but the second largest element smaller than $a _ { k - 1} + 1$, etc., i.e. the family of the first $\partial _ { k } ( m )$ elements of $\left( \begin{array} { c } { [ n ] } \\ { k - 1 } \end{array} \right)$ where

\begin{equation*} \partial _ { k } ( m ) = \left( \begin{array} { c } { a _ { k } } \\ { k - 1 } \end{array} \right) + \left( \begin{array} { c } { a _ { k } - 1 } \\ { k - 2 } \end{array} \right) + \ldots + \left( \begin{array} { c } { a _ { 1 } } \\ { 0 } \end{array} \right). \end{equation*}

The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if $\mathcal{F}$ is any $m$-element family in $\left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $m$ is given by (a1), then

\begin{equation*} | \Delta ( {\cal F} ) | \geq \partial _ { k } ( m ). \end{equation*}

There exist generalizations to similar results for other partially ordered sets, like products of chains, products of stars, the partially ordered set of subwords of $0$-$1$-words, and the partially ordered set of submatrices of a matrix.

The following result of L. Lovász is weaker but numerically easier to handle: If ${\cal F} \subseteq \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$ and $| \mathcal F | = \left( \begin{array} { l } { x } \\ { k } \end{array} \right)$ with some real $x$, where $k \leq x \leq n$, then

\begin{equation*} | \Delta ( \mathcal{F} ) | \geq \left( \begin{array} { c } { x } \\ { k - 1 } \end{array} \right). \end{equation*}

The original papers by J.B. Kruskal and G.O.H. Katona are [a3], [a4].

According to [a2], p. 1296, the Kruskal–Katona theorem is probably the most important one in finite extremal set theory.

References

[a1] K. Engel, "Sperner theory" , Encyclopedia of Mathematics and its Applications 65, Cambridge Univ. Press (1997) ISBN 0-521-45206-6 Zbl 0868.05001
[a2] P. Frankl, "Extremal set systems" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , 2 , Elsevier (1995) pp. 1293–1329
[a3] J.B. Kruskal, "The number of simplices in a complex" , Mathematical Optimization Techniques , Univ. California Press (1963) pp. 251–278. Zbl 0116.35102
[a4] G.O.H. Katona, "A theorem of finite sets" , Theory of Graphs. Proc. Colloq. Tihany , Akad. Kiadó (1966) pp. 187–207. Zbl 0313.05003 Zbl 0612.05001
How to Cite This Entry:
Kruskal-Katona theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kruskal-Katona_theorem&oldid=51587
This article was adapted from an original article by K. Engel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article