A teoria de Sperner

Teorema de Sperner Para o teorema sobre simplexes, veja o lema de Sperner.

A teoria de Sperner, em matemática discreta, descreve as maiores famílias possíveis de conjuntos finitos, nenhum dos quais contém quaisquer outros conjuntos na família. É um dos resultados centrais na teoria dos conjuntos extremos. É nomeado após Emanuel Sperner, que publicou em 1928.

Este resultado às vezes é chamado de lema de Sperner, mas o nome "tema de Sperner" também se refere a um resultado não relacionado em triangulações de coloração. Para diferenciar os dois resultados, o resultado sobre o tamanho de uma família de Sperner é agora mais comumente conhecido como teorema de Sperner.

Conteúdo 1 Declaração 2 Pedidos parciais 3 Prova 4 Generalizações 4.1 Sem cadeias longas 4.2 p-composições de um conjunto 4.3 Sem cadeias longas em p-composições de um conjunto 4.4 Analógico de geometria projetiva 4.5 Sem cadeias longas em p-composições de um espaço projetivo 5 Veja também 6 Referências 7 External links Statement A family of sets in which none of the sets is a strict subset of another is called a Sperner family, ou uma anticadeia de conjuntos, ou uma desordem. Por exemplo, a família de subconjuntos de k elementos de um conjunto de n elementos é uma família Sperner. Nenhum conjunto nesta família pode conter qualquer um dos outros, porque um conjunto contendo tem que ser estritamente maior do que o conjunto que ele contém, e nesta família todos os conjuntos têm o mesmo tamanho. O valor de k que faz com que este exemplo tenha tantos conjuntos quanto possível é n/2 se n for par, ou qualquer um dos inteiros mais próximos de n/2 se n for ímpar. Para esta escolha, o número de conjuntos na família é {estilo de exibição {tbinom {n}{l andar n/2 andar }}} .

O teorema de Sperner afirma que esses exemplos são as maiores famílias de Sperner possíveis sobre um conjunto de n elementos. Formalmente, o teorema afirma que, para cada família Sperner S cuja união tem um total de n elementos, {estilo de exibição |S|leq {alguns deles {n}{l andar n/2 andar }},} e igualdade vale se e somente se S consiste em todos os subconjuntos de um conjunto de n elementos que têm tamanho {displaystyle lfloor n/2rfloor } ou todos que têm tamanho {displaystyle lceil n/2rceil } . Partial orders Sperner's theorem can also be stated in terms of partial order width. A família de todos os subconjuntos de um conjunto de n elementos (seu conjunto de energia) pode ser parcialmente ordenado por inclusão de conjunto; nesta ordem parcial, dois elementos distintos são ditos incomparáveis ​​quando nenhum deles contém o outro. A largura de uma ordem parcial é o maior número de elementos em uma anticadeia, um conjunto de elementos incomparáveis ​​aos pares. Traduzindo esta terminologia para a linguagem dos conjuntos, um antichain é apenas uma família Sperner, e a largura da ordem parcial é o número máximo de conjuntos em uma família Sperner. Desta forma, outra maneira de enunciar o teorema de Sperner é que a largura da ordem de inclusão em um conjunto de potências é {estilo de exibição {alguns deles {n}{l andar n/2 andar }}} .

Diz-se que um conjunto graduado parcialmente ordenado tem a propriedade de Sperner quando uma de suas maiores anticadeias é formada por um conjunto de elementos que têm todos o mesmo posto.. Nesta terminologia, O teorema de Sperner afirma que o conjunto parcialmente ordenado de todos os subconjuntos de um conjunto finito, parcialmente ordenado por inclusão de conjunto, tem a propriedade Sperner.

Proof There are many proofs of Sperner's theorem, cada um levando a diferentes generalizações (veja Anderson (1987)).

A seguinte prova é devido a Lubell (1966). Seja sk o número de k-conjuntos em S. Para todos 0 ≤ k ≤ n, {estilo de exibição {n escolha lfloor {n/2}andar }geq {n escolha k}} e, portanto, {estilo de exibição {s_{k} sobre {n escolha lfloor {n/2}andar }}leq {s_{k} sobre {n escolha k}}.} Como S é uma anticadeia, podemos somar a desigualdade acima de k = 0 para n e, em seguida, aplique a desigualdade LYM para obter {soma de estilo de exibição _{k=0}^{n}{s_{k} sobre {n escolha lfloor {n/2}andar }}soma leq _{k=0}^{n}{s_{k} sobre {n escolha k}}leq 1,} que significa {estilo de exibição |S|=soma _{k=0}^{n}s_{k}leq {n escolha lfloor {n/2}andar }.} Isso completa a prova da parte 1.

Para ter igualdade, todas as desigualdades na prova anterior devem ser igualdades. Desde {estilo de exibição {n escolha lfloor {n/2}andar }={n escolha k}} se e apenas se {estilo de exibição k=lfloor {n/2}andar } ou {displaystyle lceil {n/2}rcel ,} concluímos que a igualdade implica que S consiste apenas em conjuntos de tamanhos {displaystyle lfloor {n/2}andar } ou {displaystyle lceil {n/2}rcel .} Para mesmo n que conclui a prova da parte 2.

Para n ímpar, há mais trabalho a fazer, que omitimos aqui porque é complicado. Veja Anderson (1987), pp. 3-4.

Generalizations There are several generalizations of Sperner's theorem for subsets of {estilo de exibição {matemática {P}}(E),} o poset de todos os subconjuntos de E.

No long chains A chain is a subfamily {estilo de exibição {S_{0},S_{1},pontos ,S_{r}}subseteq {matemática {P}}(E)} que é totalmente ordenado, ou seja, {estilo de exibição S_{0}subconjunto S_{1}subconjunto pontos subconjunto S_{r}} (possivelmente após a renumeração). A cadeia tem r + 1 membros e comprimento r. Uma família sem cadeia r (também chamado de família r) é uma família de subconjuntos de E que não contém cadeia de comprimento r. Floresta (1945) provou que o maior tamanho de uma família livre de r cadeia é a soma dos r maiores coeficientes binomiais {estilo de exibição {alguns deles {n}{eu}}} . O caso r = 1 é a teoria de Sperner.

p-compositions of a set In the set {estilo de exibição {matemática {P}}(E)^{p}} de p-tuplas de subconjuntos de E, dizemos uma p-tupla {estilo de exibição (S_{1},pontos ,S_{p})} é ≤ outro, {estilo de exibição (T_{1},pontos ,T_{p}),} E se {estilo de exibição S_{eu}subseq T_{eu}} para cada i = 1,2,...,p. Nós chamamos {estilo de exibição (S_{1},pontos ,S_{p})} uma composição p de E se os conjuntos {estilo de exibição S_{1},pontos ,S_{p}} formar uma partição de E. Meshalkin (1963) provou que o tamanho máximo de uma anticadeia de composições p é o maior coeficiente multinomial p {estilo de exibição {alguns deles {n}{n_{1} n_{2} dots n_{p}}},} isso é, o coeficiente em que todos os ni são o mais próximo possível (ou seja, diferem no máximo 1). Meshalkin provou isso provando uma desigualdade LYM generalizada.

O caso p = 2 é a teoria de Sperner, porque então {estilo de exibição S_{2}=Esetminus S_{1}} e as premissas se reduzem aos conjuntos {estilo de exibição S_{1}} ser uma família Sperner.

No long chains in p-compositions of a set Beck & Zaslavsky (2002) combinou os teoremas de Erdös e Meshalkin adaptando a prova de Meshalkin de sua desigualdade LYM generalizada. Eles mostraram que o maior tamanho de uma família de p-composições tal que os conjuntos na i-ésima posição das p-tuplas, ignorando duplicações, são livres de cadeia r, para cada {estilo de exibição i=1,2,pontos ,p-1} (mas não necessariamente para i = p), não é maior que a soma dos {estilo de exibição r^{p-1}} maiores coeficientes p-multinomiais.

Projective geometry analog In the finite projective geometry PG(d, Fq) de dimensão d sobre um corpo finito de ordem q, deixar {estilo de exibição {matemática {eu}}(p,F_{q})} ser a família de todos os subespaços. Quando parcialmente ordenado por inclusão de conjunto, essa família é uma treliça. Rota & Harper (1971) provou que o maior tamanho de uma anticadeia em {estilo de exibição {matemática {eu}}(p,F_{q})} é o maior coeficiente gaussiano {estilo de exibição {começar{bmatriz}d+1conhecido{bmatriz}};} este é o análogo da geometria projetiva, ou q-analógico, da teoria de Sperner.

Eles provaram ainda que o maior tamanho de uma família livre de cadeia R em {estilo de exibição {matemática {eu}}(p,F_{q})} é a soma dos r maiores coeficientes gaussianos. Sua prova é por um análogo projetivo da desigualdade LYM.

No long chains in p-compositions of a projective space Beck & Zaslavsky (2003) obteve uma generalização do tipo Meshalkin do teorema de Rota-Harper. Em PG(d, Fq), uma sequência de Meshalkin de comprimento p é uma sequência {estilo de exibição (UMA_{1},ldots ,UMA_{p})} de subespaços projetivos tal que nenhum subespaço próprio de PG(d, Fq) contém todos eles e suas dimensões somam {estilo de exibição d-p+1} . O teorema é que uma família de sequências de Meshalkin de comprimento p em PG(d, Fq), tal que os subespaços que aparecem na posição i das sequências não contêm cadeia de comprimento r para cada {estilo de exibição i=1,2,pontos ,p-1,} não é mais do que a soma do maior {estilo de exibição r^{p-1}} das quantidades {estilo de exibição {começar{bmatriz}d+1n_{1} n_{2} dots n_{p}fim{bmatriz}}q^{s_{2}(n_{1},ldots ,n_{p})},} Onde {estilo de exibição {começar{bmatriz}d+1n_{1} n_{2} dots n_{p}fim{bmatriz}}} (em que assumimos que {estilo de exibição d+1=n_{1}+cdots +n_{p}} ) denota o coeficiente p-Gaussiano {estilo de exibição {começar{bmatriz}d+1n_{1}fim{bmatriz}}{começar{bmatriz}d+1-n_{1}\n_{2}fim{bmatriz}}cdots {começar{bmatriz}d+1-(n_{1}+cdots +n_{p-1})\n_{p}fim{bmatriz}}} e {estilo de exibição s_{2}(n_{1},ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+cdots +n_{p-1}n_{p},} a segunda função simétrica elementar dos números {estilo de exibição n_{1},n_{2},pontos ,n_{p}.} See also Mathematics portal Dilworth's theorem References Anderson, Ian (1987), Combinatória de conjuntos finitos, imprensa da Universidade de Oxford. Beck, Matias; Zaslavsky, Thomas (2002), "Um mais curto, mais simples, prova mais forte dos limites de Meshalkin-Hochberg-Hirsch em anticadeias componentes", Jornal de Teoria Combinatória, Série A, 100 (1): 196-199, arXiv:math/0112068, doi:10.1006/jcta.2002.3295, MR 1932078, S2CID 8136773. Beck, Matias; Zaslavsky, Thomas (2003), "Um teorema de Meshalkin para geometrias projetivas", Jornal de Teoria Combinatória, Série A, 102 (2): 433-441, arXiv:matemática/0112069, doi:10.1016/S0097-3165(03)00049-9, MR 1979545, S2CID 992137. Engel, Konrad (1997), Teoria de Sperner, Enciclopédia de Matemática e suas Aplicações, volume. 65, Cambridge: Cambridge University Press, p. x+417, doi:10.1017/CBO9780511574719, ISBN 0-521-45206-6, MR 1429390. Engel, K. (2001) [1994], "Teorema de Sperner", Enciclopédia de Matemática, EMS Press Erdős, P. (1945), "Em um lema de Littlewood e Offord" (PDF), Boletim da American Mathematical Society, 51 (12): 898–902, doi:10.1090/S0002-9904-1945-08454-7, MR 0014608 Lubell, D. (1966), "Uma pequena prova do lema de Sperner", Jornal de Teoria Combinatória, 1 (2): 299, doi:10.1016/S0021-9800(66)80035-2, MR 0194348. Meshalkin, L.D.. (1963), "Generalização do teorema de Sperner sobre o número de subconjuntos de um conjunto finito", Teoria da Probabilidade e Suas Aplicações (em russo), 8 (2): 203-204, doi:10.1137/1108023. Rota, Gian-Carlo; Harpista, eu. H. (1971), "Teoria de correspondência, uma introdução", Avanços em Probabilidade e Tópicos Relacionados, Volume. 1, Nova york: Dekker, pp. 169-215, MR 0282855. Sperner, Emanuel (1928), "Um teorema sobre subconjuntos de um conjunto finito", Diário de Matemática (em alemão), 27 (1): 544-548, doi:10.1007/BF01171114, HDL:10338.dmlcz/127405, JFM 54.0090.06, S2CID 123451223. Links externos Teorema de Sperner no cut-the-knot Teorema de Sperner na wiki polymath1 Categorias: Definir famíliasTópicos fatoriais e binomiais