Desigualdade de Lubell-Yamamoto-Meshalkin - Lubell–Yamamoto–Meshalkin inequality

Em matemática combinatória , a desigualdade de Lubell – Yamamoto – Meshalkin , mais comumente conhecida como a desigualdade LYM , é uma desigualdade nos tamanhos dos conjuntos em uma família Sperner , comprovada por Bollobás (1965) , Lubell (1966) , Meshalkin (1963) , e Yamamoto (1954) . Seu nome vem das iniciais de três de seus descobridores. Para incluir as iniciais de todos os quatro descobridores, às vezes é chamada de desigualdade YBLM .

Essa desigualdade pertence ao campo da combinatória de conjuntos e tem muitas aplicações em combinatória. Em particular, pode ser usado para provar o teorema de Sperner . Seu nome também é usado para desigualdades semelhantes.

Declaração do teorema

Deixe L ser um n conjunto -element, deixar Um ser uma família de subconjuntos de L de tal modo que nenhum conjunto em A é um subconjunto de outro conjunto em um , e deixar um _K denotam o número de conjuntos de tamanho k em um . Então

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

A prova de Lubell

Lubell (1966) prova a desigualdade de Lubell – Yamamoto – Meshalkin por um argumento de dupla contagem no qual ele conta as permutações de U de duas maneiras diferentes. Primeiro, contando todas as permutações de U identificadas com {1,…, n } diretamente, descobre-se que há n ! deles. Mas em segundo lugar, pode-se gerar uma permutação (isto é, uma ordem) dos elementos de U selecionando um conjunto S em A e escolhendo um mapa que envia {1,…, | S | } Para S . If | S | =  k , o conjunto S está associado desta forma com k ! ( n  -  k )! permutações, e em cada um deles a imagem dos primeiros k elementos de U é exatamente S . Cada permutação só pode ser associada a um único conjunto em A , pois se dois prefixos de uma permutação formaram ambos conjuntos em A, então um seria um subconjunto do outro. Portanto, o número de permutações que podem ser geradas por este procedimento é

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

Uma vez que este número é no máximo o número total de todas as permutações,

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

Finalmente, dividindo a desigualdade acima por n ! leva ao resultado.

Referências

• 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), "A short proof of Sperner's lemma", Journal of Combinatorial Theory , 1 (2): 299, doi : 10.1016 / S0021-9800 (66) 80035-2 , MR  0194348.

• Meshalkin, LD (1963), "Generalização do teorema de Sperner sobre o número de subconjuntos de um conjunto finito", Teoria da probabilidade e suas aplicações , 8 (2): 203–204, doi : 10.1137 / 1108023 , MR  0150049.

• Yamamoto, Koichi (1954), "Logarithmic order of free distributive rettice", Journal of the Mathematical Society of Japan , 6 (3-4): 343-353, doi : 10.2969 / jmsj / 00630343 , MR  0067086.