Namespaces
Variants
Actions

Difference between revisions of "Kruskal-Katona theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (gt to >)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300601.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300602.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300603.png" /> (cf. also [[Sperner property|Sperner property]]; [[Sperner theorem|Sperner theorem]]). The elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300604.png" /> can be linearly ordered in the following way: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300605.png" /> if the largest element in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300606.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300607.png" /> differ is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300608.png" /> (cf. also [[Totally ordered set|Totally ordered set]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k1300609.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006010.png" />, is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006011.png" />th element in this order, then
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,  
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
Out of 58 formulas, 58 were replaced by TEX code.-->
  
since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006013.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006014.png" />-element subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006015.png" /> have maximal element smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006017.png" /> have maximal element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006018.png" /> but the second largest element smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006019.png" />, etc.. Equation (a1) is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006021.png" />-representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006023.png" /> (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006024.png" />, one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006027.png" />). This (unique) representation can be found directly by choosing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006028.png" /> maximal such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006030.png" /> maximal such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006031.png" />, etc..
+
{{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
  
For a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006032.png" />, the lower shadow of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006033.png" /> is defined by
+
\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}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006034.png" /></td> </tr></table>
+
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..
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006035.png" /> is given as above, then the lower shadow of the family of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006036.png" /> elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006037.png" /> is the family of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006038.png" />-element subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006039.png" /> having maximal element smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006040.png" />, of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006041.png" />-element subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006042.png" /> having maximal element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006043.png" />, but the second largest element smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006044.png" />, etc., i.e. the family of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006045.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006046.png" /> where
+
For a family ${\cal F} \subseteq \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right)$, the lower shadow of $\mathcal{F}$ is defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006047.png" /></td> </tr></table>
+
\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*}
  
The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006048.png" /> is any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006049.png" />-element family in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006051.png" /> is given by (a1), then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006052.png" /></td> </tr></table>
+
\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*}
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006053.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006054.png" />-words, and the partially ordered set of submatrices of a matrix.
+
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 following result of L. Lovász is weaker but numerically easier to handle: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006056.png" /> with some real <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006057.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006058.png" />, then
+
\begin{equation*} | \Delta ( {\cal F} ) | \geq \partial _ { k } ( m ). \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130060/k13006059.png" /></td> </tr></table>
+
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 [[#References|[a3]]], [[#References|[a4]]].
 
The original papers by J.B. Kruskal and G.O.H. Katona are [[#References|[a3]]], [[#References|[a4]]].
Line 28: Line 36:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Engel,  "Sperner theory" , Cambridge Univ. Press  (1997)</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</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></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">[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">[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>

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=15000
This article was adapted from an original article by K. Engel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article