Accueil🇫🇷Chercher

Inégalité de Lubell-Yamamoto-Meshalkin

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é

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

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

(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, nos 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 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
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.