Inégalité de Lubell-Yamamoto-Meshalkin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, l'inégalité de Lubell-Yamamoto-Meshalkin, ou inégalité LYM, est une inégalité combinatoire sur les tailles des ensembles d'une famille de Sperner, démontrée par Bollobás[1], Lubell[2], Meshalkin[3] et Yamamoto[4].

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é[modifier | modifier le code]

Soient U un ensemble à n éléments, A une famille de parties de U dont aucune n'est incluse dans une autre, et ak le nombre de parties de taille k dans la famille A. Alors,

Démonstration de Lubell[modifier | modifier le code]

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 bijection s : {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,

ce qui conclut.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lubell–Yamamoto–Meshalkin inequality » (voir la liste des auteurs).

  1. (en) B. Bollobás, « On generalized graphs », Acta Math. Hungar., vol. 16, no 3-4,‎ , p. 447-452 (DOI 10.1007/BF01904851)
  2. (en) D. Lubell, « A short proof of Sperner's lemma », JCT, vol. 1, no 2,‎ , p. 299 (DOI 10.1016/S0021-9800(66)80035-2)
  3. (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 (DOI 10.1137/1108023)
  4. (en) Koichi Yamamoto, « Logarithmic order of free distributive lattice », J. Math. Soc. Japan, vol. 6,‎ , p. 343-353 (lire en ligne)
  5. (en) M. Beck, X. Wang et T. Zaslavsky, « A Unifying Generalization of Sperner's Theorem », dans E. Gyari, G. O. H. Katona (en) et L. Lovász, More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal (en), Springer, coll. « Bolyai Society Mathematical Studies » (no 15), , p. 9-24, arXiv:math/0112067