Elle a beaucoup d'applications en combinatoire ; en particulier, elle peut être utilisée pour démontrer le lemme de Sperner. Ce terme est aussi utilisé pour désigner des inégalités similaires[5].
Énoncé
Soient U un ensemble à n éléments, A une famille de parties de U dont aucune n'est incluse dans une autre, et akle nombre de parties de taille k dans la famille A. Alors,
Démonstration de Lubell
Lubell (en 1966) démontre cette inégalité LYM par un argument de double dénombrement, dans lequel il dénombre les permutations de U = {1, … n} de deux façons. D'abord, par dénombrement direct, il y en a n!. Mais d'autre part, on peut choisir un membre S de la famille A et une bijections : {1, … , |S|} → S, puis compléter s en une permutation de U. Si |S| = k, on lui associe ainsi k!(n – k)! permutations. Chaque permutation est associée à au plus un membre S de A. En effet par l'absurde, si s est une permutation associée à deux membres, S et T de A pris tels que |S|≤|T|, alors l'image de {1, … , |S|} par s est S, et est incluse dans T. Par conséquent, le nombre des permutations engendrées par cette construction est
Comme ce nombre est au plus égal au nombre total de permutations,
↑(en) L. D. Meshalkin, « Generalization of Sperner's theorem on the number of subsets of a finite set », Th. Prob. Appl., vol. 8, no 2, , p. 203-204 (DOI10.1137/1108023)
↑(en) Koichi Yamamoto, « Logarithmic order of free distributive lattice », J. Math. Soc. Japan, vol. 6, , p. 343-353 (lire en ligne)
↑(en) M. Beck, X. Wang et T. Zaslavsky, « A Unifying Generalization of Sperner's Theorem », dans E. Gyari, G. O. H. Katona et L. Lovász, More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal, Springer, coll. « Bolyai Society Mathematical Studies » (no 15), , p. 9-24, arXiv:math/0112067