Antilant

Un antilanț  este un subset al unui set parțial ordonat în care oricare două elemente distincte sunt incomparabile.

Cardinalitatea maximă a unui antilanț al unui set parțial ordonat se numește lățimea sa ; prin teorema lui Dilworth , lățimea este, de asemenea, egală cu numărul minim de lanțuri (subseturi complet ordonate) în care o mulțime poate fi împărțită. În consecință, înălțimea unei mulțimi parțial ordonate (lungimea celui mai lung lanț al său) este egală, conform teoremei lui Mirsky , cu numărul minim de antilanțuri în care această mulțime poate fi împărțită.

Familia tuturor antilanțurilor dintr-o mulțime finită parțial ordonată poate fi echipată cu operații de unire și intersecție, transformându-le într- o rețea distributivă . Pentru un sistem parțial ordonat de toate submulțimile unei mulțimi finite ordonate după includerea mulțimii, antilanțurile sunt numite familii Sperner , iar rețeaua lor este o rețea distributivă liberă cu un număr Dedekind de elemente. În general, problema numărării numărului de antilanțuri ale unei mulțimi finite parțial ordonate este ♯P-complet .