Teorema di Sperner

Il teorema di Sperner è un risultato fondamentale della combinatoria che descrive la dimensione massima di una famiglia di sottoinsiemi di un insieme finito in cui nessun insieme è contenuto in un altro. Tali famiglie sono chiamate famiglie di Sperner.

Prende il nome dal matematico tedesco Emanuel Sperner, che lo dimostrò nel 1928.

Sia ${\displaystyle X}$ un insieme con ${\displaystyle n}$ elementi. Una famiglia ${\displaystyle {\mathcal {F}}}$ di sottoinsiemi di ${\displaystyle X}$ è detta famiglia di Sperner se per ogni ${\displaystyle A,B\in {\mathcal {F}}}$ con ${\displaystyle A\neq B}$ vale:

${\displaystyle A\nsubseteq B}$ e ${\displaystyle B\nsubseteq A}$

Il teorema afferma che:

${\displaystyle |{\mathcal {F}}|\leq {\binom {n}{\lfloor n/2\rfloor }}}$

Inoltre, l'uguaglianza si verifica se e solo se ${\displaystyle {\mathcal {F}}}$ è costituita da tutti i sottoinsiemi di ${\displaystyle X}$ di cardinalità ${\displaystyle \lfloor n/2\rfloor }$ o da tutti i sottoinsiemi di ${\displaystyle X}$ di cardinalità ${\displaystyle \lceil n/2\rceil }$.

L'insieme delle parti di ${\displaystyle X}$ può essere visto come un insieme parzialmente ordinato rispetto all'inclusione. In questo contesto, una famiglia di Sperner è un'anticatena (in inglese antichain), cioè un insieme di elementi a due a due incomparabili.

Una dimostrazione del teorema utilizza la disuguaglianza di Lubell-Yamamoto-Meshalkin (LYM). Se ${\displaystyle s_{k}}$ indica il numero di insiemi di cardinalità ${\displaystyle k}$ nella famiglia ${\displaystyle {\mathcal {F}}}$, allora:

${\displaystyle \sum _{k=0}^{n}{\frac {s_{k}}{\binom {n}{k}}}\leq 1}$

da cui segue il risultato.

• (EN) Ian Anderson, Combinatorics of Finite Sets, Oxford University Press, 1987.
• (EN) Matthias Beck e Thomas Zaslavsky, A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains, in Journal of Combinatorial Theory, collana Series A, vol. 100, n. 1, 2002, pp. 196–199, DOI:10.1006/jcta.2002.3295, arXiv:math/0112068.
• (EN) Matthias Beck e Thomas Zaslavsky, A Meshalkin theorem for projective geometries, in Journal of Combinatorial Theory, collana Series A, vol. 102, n. 2, 2003, pp. 433–441, DOI:10.1016/S0097-3165(03)00049-9, arXiv:math/0112069.
• (EN) Konrad Engel, Sperner theory, collana Encyclopedia of Mathematics and its Applications, vol. 65, Cambridge, Cambridge University Press, 1997, p. x+417, DOI:10.1017/CBO9780511574719, ISBN 0-521-45206-6.
• (EN) P. Erdős, On a lemma of Littlewood and Offord (PDF), in Bulletin of the American Mathematical Society, vol. 51, n. 12, 1945, pp. 898–902, DOI:10.1090/S0002-9904-1945-08454-7.
• (EN) D. Lubell, A short proof of Sperner's lemma, in Journal of Combinatorial Theory, vol. 1, n. 2, 1966, p. 299, DOI:10.1016/S0021-9800(66)80035-2.
• (RU) L.D. Meshalkin, Generalization of Sperner's theorem on the number of subsets of a finite set, in Theory of Probability and Its Applications, vol. 8, n. 2, 1963, pp. 203–204, DOI:10.1137/1108023.
• (EN) Gian-Carlo Rota e L. H. Harper, Matching theory, an introduction, in Advances in Probability and Related Topics, Vol. 1, New York, Dekker, 1971, pp. 169–215.
• (DE) Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, in Mathematische Zeitschrift, vol. 27, n. 1, 1928, pp. 544–548, DOI:10.1007/BF01171114, JFM 54.0090.06, hdl:10338.dmlcz/127405.

• Combinatoria
• Teoria degli ordini
• Disuguaglianza di Lubell-Yamamoto-Meshalkin