Desigualdad de Lubell-Yamamoto-Meshalkin

En matemáticas combinatorias , la desigualdad de Lubell-Yamamoto-Meshalkin , más comúnmente conocida como desigualdad LYM , es una desigualdad sobre los tamaños de los conjuntos en una familia de Sperner , demostrada por Bollobás (1965), Lubell (1966), Meshalkin (1963) y Yamamoto (1954). Recibe su nombre por las iniciales de tres de sus descubridores. Para incluir las iniciales de los cuatro descubridores, a veces se la denomina desigualdad YBLM .

Esta desigualdad pertenece al campo de la combinatoria de conjuntos y tiene muchas aplicaciones en combinatoria. En particular, se puede utilizar para demostrar el teorema de Sperner . Su nombre también se utiliza para desigualdades similares.

Enunciado del teorema

Sea U un conjunto de n elementos, sea A una familia de subconjuntos de U tales que ningún conjunto en A es un subconjunto de otro conjunto en A , y sea a _k el número de conjuntos de tamaño k en A . Entonces

${\displaystyle \sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.}$

Prueba de Lubell

Lubell (1966) demuestra la desigualdad de Lubell–Yamamoto–Meshalkin mediante un argumento de doble conteo en el que cuenta las permutaciones de U de dos maneras diferentes. Primero, contando todas las permutaciones de U identificadas con {1, …, n } directamente, se encuentra que hay n ! de ellas. Pero en segundo lugar, se puede generar una permutación (es decir, un orden) de los elementos de U seleccionando un conjunto S en A y eligiendo una función que envíe {1, … , | S | } a S . Si | S | =  k , el conjunto S está asociado de esta manera con k !( n  −  k )! permutaciones, y en cada una de ellas la imagen de los primeros k elementos de U es exactamente S . Cada permutación solo puede estar asociada con un único conjunto en A , ya que si dos prefijos de una permutación formaran conjuntos en A, entonces uno sería un subconjunto del otro. Por lo tanto, el número de permutaciones que se pueden generar mediante este procedimiento es

${\displaystyle \sum _{S\in A}|S|!(n-|S|)!=\sum _{k=0}^{n}a_{k}k!(n-k)!.}$

Dado que este número es como máximo el número total de todas las permutaciones,

${\displaystyle \sum _{k=0}^{n}a_{k}k!(n-k)!\leq n!.}$

Finalmente, dividiendo la desigualdad anterior por n ! obtenemos el resultado.

Referencias

• Bollobás, B. (1965), "Sobre gráficos generalizados", Acta Mathematica Academiae Scientiarum Hungaricae , 16 (3–4): 447–452, doi : 10.1007/BF01904851 , MR  0183653, S2CID  122892253.

• Lubell, D. (1966), "Una breve prueba del lema de Sperner", Journal of Combinatorial Theory , 1 (2): 299, doi : 10.1016/S0021-9800(66)80035-2 , MR  0194348.

• Meshalkin, LD (1963), "Generalización del teorema de Sperner sobre el número de subconjuntos de un conjunto finito", Teoría de la probabilidad y sus aplicaciones , 8 (2): 203–204, doi :10.1137/1108023, MR  0150049.

• Yamamoto, Koichi (1954), "Orden logarítmico de red distributiva libre", Journal of the Mathematical Society of Japan , 6 (3–4): 343–353, doi : 10.2969/jmsj/00630343 , MR  0067086.