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,

\sum_{k=0}^n\frac{a_k}{{n\choose k}}\le1.

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, car deux « préfixes » d'une même permutation sont inclus l'un dans l'autre. Par conséquent, le nombre des permutations engendrées par cette construction est

\sum_{S\in A}|S|!(n-|S|)!=\sum_{k=0}^n a_k k! (n-k)!.

Comme ce nombre est au plus égal au nombre total de permutations,

\sum_{k=0}^n a_k k! (n-k)!\le n!,

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,‎ 1965, p. 447-452 (DOI 10.1007/BF01904851)
  2. (en) D. Lubell, « A short proof of Sperner's lemma », JCT, vol. 1, no 2,‎ 1966, 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,‎ 1963, p. 203-204 (DOI 10.1137/1108023)
  4. (en) Koichi Yamamoto, « Logarithmic order of free distributive lattice », J. Math. Soc. Japan, vol. 6,‎ 1954, 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),‎ 2006, p. 9-24, arXiv:math/0112067