Numim lant o submultime a lui \( X \) in care oricare doua elemente sunt comparabile si antilant o submultime a lui \( X \) in care oricare doua elemente nu sunt comparabile. Latimea multimii \( X \) este cardinalul celui mai mare antilant.
Teorema lui Dilworth - Demonstrati ca daca \( X \) are latimea \( k \) atunci \( X \) se scrie ca reuniunea a \( k \) lanturi.
Desi pare cam abstracta, problema are unele aplicatii imediate:
1. Demonstrati ca un sir care contine \( mn+1 \) elemente contine un subsir crescator cu \( m+1 \) sau un subsir descrescator cu \( n+1 \) elemente
2. Demonstrati ca daca avem un sir de \( n^2+1 \) numere naturale nenule astfel incat in orice subsir \( x_1,...,x_{n+1} \) exista \( k<l \) astfel incat \( x_k |x_l \). Atunci exista un subsir al acestuia cu \( n+1 \) elemente astfel incat fiecare termen il divide pe urmatorul.
(Baraj 2005
)3. Problema de aici cred ca are o rezolvare tot cu teorema asta, dar nu am gasit o relatie de ordine potrivita inca.
