En matemática combinatoria , la desigualdad de Lubell-Yamamoto-Meshalkin , más comúnmente conocida como desigualdad LYM , es una desigualdad en los tamaños de conjuntos en una familia de Sperner , demostrada por Bollobás (1965) , Lubell (1966) , Meshalkin (1963) , y Yamamoto (1954) . Lleva el nombre de las iniciales de tres de sus descubridores. Para incluir las iniciales de los cuatro descubridores, a veces se denomina desigualdad YBLM .
Esta desigualdad pertenece al campo de la combinatoria de conjuntos y tiene muchas aplicaciones en la combinatoria. En particular, se puede utilizar para probar el teorema de Sperner . Su nombre también se usa para desigualdades similares.
Declaración del teorema
Vamos U ser un n conjunto -elemento, vamos A una familia de subconjuntos de U de tal modo que ningún conjunto en A es un subconjunto de otro conjunto en A , y dejar que una k denota el número de conjuntos de tamaño k en A . Luego
La prueba de Lubell
Lubell (1966) prueba la desigualdad de Lubell-Yamamoto-Meshalkin mediante un argumento de doble recuento en el que cuenta las permutaciones de U de dos formas diferentes. Primero, contando todas las permutaciones de U identificadas con {1,…, n } directamente, se encuentra que hay n ! de ellos. 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 un mapa que envíe {1,…, | S | } A S . Si | S | = k , el conjunto S se asocia de esta manera con k ! ( n - k )! permutaciones, y en cada uno de ellos la imagen de los primeros k elementos de U es exactamente S . Cada permutación solo puede asociarse con un único conjunto en A , porque 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 puede generar este procedimiento es
Dado que este número es como máximo el número total de todas las permutaciones,
Finalmente dividiendo la desigualdad anterior por n ! conduce al resultado.
Referencias
- Bollobás, B. (1965), "On generalized graphs", 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 la red distributiva libre", Revista de la Sociedad Matemática de Japón , 6 (3–4): 343–353, doi : 10.2969 / jmsj / 00630343 , MR 0067086.