Namespaces
Variants
Actions

Difference between revisions of "Greene-Kleitman theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: expand bibliodata)
(TeX done)
Line 1: Line 1:
Dilworth's theorem [[#References|[a1]]] states that in a finite [[Partially ordered set|partially ordered set]] the [[Width of a partially ordered set|width]], the maximal size of an independent set (i.e., an [[anti-chain]], a set of mutually incomparable elements) is equal to the minimal number of chains needed to cover the partially ordered set (a chain is a set of mutually comparable elements, a [[totally ordered set|totally ordered subset]]).
+
Dilworth's theorem [[#References|[a1]]] states that in a finite [[partially ordered set]] the [[Width of a partially ordered set|width]], the maximal size of an independent set (i.e., an [[anti-chain]], a set of mutually incomparable elements) is equal to the minimal number of chains needed to cover the partially ordered set (a chain is a set of mutually comparable elements, a [[totally ordered set|totally ordered subset]]).
  
C. Greene and D.J. Kleitman asked what happens if in the statement of this theorem the notion of an  "independent set"  is replaced by the more general notion of  "union of k-independent sets" , also called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102202.png" />-independent set. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102203.png" /> are independent sets. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102204.png" /> is a partition of the [[Graph|graph]] into chains, then each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102205.png" /> meets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102206.png" /> in at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102207.png" /> points. Hence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102208.png" /> (the right-hand side of this inequality is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022010.png" />-norm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022011.png" />). The analogue of Dilworth's theorem, which is the Greene–Kleitman theorem [[#References|[a4]]], is that this trivial bound can, in fact, be attained: The maximal size of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022012.png" />-independent set in a partially ordered set is the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022013.png" />-norm of a partition of the partially ordered set into chains.
+
C. Greene and D.J. Kleitman asked what happens if in the statement of this theorem the notion of an  "independent set"  is replaced by the more general notion of  "union of $k$ independent sets" , also called a $k$-independent set. Suppose that $A_1,\ldots,A_k$ are independent sets. If $\mathcal{C}=\{C_1,\ldots,C_m\}$ is a partition of the set into chains, then each $C_i$ meets $\cup_{j\le k}A _j$ in at most $\min(|C_i|,k)$ points. Hence  
 +
$$
 +
\left\vert \cup_{j\le k} A_j \right\vert \le \sum_{i\le m} \min(|C_i|,k)
 +
$$
 +
(the right-hand side of this inequality is called the $k$-norm of $\mathcal{C}$). The analogue of Dilworth's theorem, which is the Greene–Kleitman theorem [[#References|[a4]]], is that this trivial bound can, in fact, be attained: The maximal size of a $k$-independent set in a partially ordered set is the minimal $k$-norm of a partition of the partially ordered set into chains.
  
Dilworth's theorem has an easy  "dual"  version: In any partially ordered set the minimal number of independent sets needed to cover all vertices is equal to the maximal size of a chain in the partially ordered set (just take the covering system of independent sets to be the levels of the partially ordered set, where a level is the set of all vertices of a given height). This theorem, too, has a  "k-analogue" , proven by Greene [[#References|[a3]]]. Let a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022015.png" />-chain be defined as a union of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022016.png" /> chains, and take the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022017.png" />-norm of a partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022018.png" /> of the partially ordered set into independent sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022019.png" /> to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022020.png" />.
+
Dilworth's theorem has an easy  "dual"  version: In any partially ordered set the minimal number of independent sets needed to cover all vertices is equal to the maximal size of a chain in the partially ordered set (just take the covering system of independent sets to be the levels of the partially ordered set, where a level is the set of all vertices of a given height). This theorem, too, has a  "$k$-analogue" , proven by Greene [[#References|[a3]]]. Let a $k$-chain be defined as a union of $k$ chains, and take the $k$-norm of a partition $\mathcal{P}$ of the partially ordered set into independent sets $I_1,\ldots,I_m$ to be $\sum_{j\le m}\min(|I_j|,k)$.
  
Then (Greene's theorem): The maximal size of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022021.png" />-chain is equal to the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022022.png" />-norm of a partition into independent sets.
+
Then (Greene's theorem): The maximal size of a $k$-chain is equal to the minimal $k$-norm of a partition into independent sets.
  
 
An elegant proof for both these results simultaneously is given in [[#References|[a2]]].
 
An elegant proof for both these results simultaneously is given in [[#References|[a2]]].
Line 16: Line 20:
 
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Greene,  D.J. Kleitman,  "The structure of Sperner $k$-families"  ''J. Combin. Th. A'' , '''20'''  (1976)  pp. 41–68  {{ZBL|0355.05027}}</TD></TR>
 
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Greene,  D.J. Kleitman,  "The structure of Sperner $k$-families"  ''J. Combin. Th. A'' , '''20'''  (1976)  pp. 41–68  {{ZBL|0355.05027}}</TD></TR>
 
</table>
 
</table>
 +
 +
{{TEX|done}}

Revision as of 19:17, 1 November 2017

Dilworth's theorem [a1] states that in a finite partially ordered set the width, the maximal size of an independent set (i.e., an anti-chain, a set of mutually incomparable elements) is equal to the minimal number of chains needed to cover the partially ordered set (a chain is a set of mutually comparable elements, a totally ordered subset).

C. Greene and D.J. Kleitman asked what happens if in the statement of this theorem the notion of an "independent set" is replaced by the more general notion of "union of $k$ independent sets" , also called a $k$-independent set. Suppose that $A_1,\ldots,A_k$ are independent sets. If $\mathcal{C}=\{C_1,\ldots,C_m\}$ is a partition of the set into chains, then each $C_i$ meets $\cup_{j\le k}A _j$ in at most $\min(|C_i|,k)$ points. Hence $$ \left\vert \cup_{j\le k} A_j \right\vert \le \sum_{i\le m} \min(|C_i|,k) $$ (the right-hand side of this inequality is called the $k$-norm of $\mathcal{C}$). The analogue of Dilworth's theorem, which is the Greene–Kleitman theorem [a4], is that this trivial bound can, in fact, be attained: The maximal size of a $k$-independent set in a partially ordered set is the minimal $k$-norm of a partition of the partially ordered set into chains.

Dilworth's theorem has an easy "dual" version: In any partially ordered set the minimal number of independent sets needed to cover all vertices is equal to the maximal size of a chain in the partially ordered set (just take the covering system of independent sets to be the levels of the partially ordered set, where a level is the set of all vertices of a given height). This theorem, too, has a "$k$-analogue" , proven by Greene [a3]. Let a $k$-chain be defined as a union of $k$ chains, and take the $k$-norm of a partition $\mathcal{P}$ of the partially ordered set into independent sets $I_1,\ldots,I_m$ to be $\sum_{j\le m}\min(|I_j|,k)$.

Then (Greene's theorem): The maximal size of a $k$-chain is equal to the minimal $k$-norm of a partition into independent sets.

An elegant proof for both these results simultaneously is given in [a2].

References

[a1] R.P. Dilworth, "A decomposition theorem for partially ordered sets" Ann. of Math. , 51 (1950) pp. 161–166 Zbl 0038.02003
[a2] A. Frank, "On chain and antichain families of a partially ordered set" J. Combin. Th. B , 29 (1980) pp. 176–184 Zbl 0443.06003
[a3] C. Greene, "Some partitions associated with a partially ordered set" J. Combin. Th. A , 20 (1976) pp. 69–79 Zbl 0323.06002
[a4] C. Greene, D.J. Kleitman, "The structure of Sperner $k$-families" J. Combin. Th. A , 20 (1976) pp. 41–68 Zbl 0355.05027
How to Cite This Entry:
Greene-Kleitman theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Greene-Kleitman_theorem&oldid=42242
This article was adapted from an original article by R. Aharoni (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article