Teorema de Dilworth - Dilworth's theorem

Em matemática , nas áreas de teoria da ordem e combinatória , o teorema de Dilworth caracteriza a largura de qualquer conjunto finito parcialmente ordenado em termos de uma partição da ordem em um número mínimo de cadeias . Recebeu o nome do matemático Robert P. Dilworth  ( 1950 ).

Uma anticadeia em um conjunto parcialmente ordenado é um conjunto de elementos em que dois não são comparáveis ​​entre si, e uma cadeia é um conjunto de elementos em que cada dois é comparável. Uma decomposição em cadeia é uma partição dos elementos da ordem em cadeias disjuntas . O teorema de Dilworth afirma que, em qualquer conjunto finito parcialmente ordenado, a maior anticadeia tem o mesmo tamanho que a menor decomposição em cadeia. Aqui, o tamanho da anticadeia é o seu número de elementos e o tamanho da decomposição da cadeia é o seu número de cadeias. A largura da ordem parcial é definida como o tamanho comum da decomposição da antichain e da cadeia.

Uma versão do teorema para conjuntos parcialmente ordenados infinitos afirma que, quando existe uma decomposição em muitas cadeias finitas, ou quando existe um limite superior finito no tamanho de uma anticadeia, os tamanhos da maior anticadeia e da menor decomposição em cadeia são novamente iguais.

Prova indutiva

A seguinte prova por indução sobre o tamanho do conjunto parcialmente ordenado é baseada na de Galvin  ( 1994 ). ${\ displaystyle P}$

Let Ser um conjunto finito parcialmente ordenado. O teorema é trivialmente válido se estiver vazio. Então, suponha que tenha pelo menos um elemento, e deixe ser um elemento máximo de . ${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle a}$${\ displaystyle P}$

Por indução, assumimos que para algum inteiro o conjunto parcialmente ordenado pode ser coberto por cadeias disjuntas e tem pelo menos uma anticadeia de tamanho . Claramente, para . Pois , deixe ser o elemento máximo em que pertence a uma antichain de tamanho em e conjunto . Afirmamos que é uma anticadeia. Deixe ser uma antichain de tamanho que contém . Fixe índices distintos arbitrários e . Então . Deixe . Então , pela definição de . Isso implica que , desde então . Ao trocar os papéis de e neste argumento, também temos . Isso verifica se é uma anticadeia. ${\ displaystyle k}$${\ displaystyle P ': = P \ setminus \ {a \}}$${\ displaystyle k}$${\ displaystyle C_ {1}, \ dots, C_ {k}}$${\ displaystyle A_ {0}}$${\ displaystyle k}$${\ displaystyle A_ {0} \ cap C_ {i} \ neq \ emptyset}$${\ displaystyle i = 1,2, \ dots, k}$${\ displaystyle i = 1,2, \ dots, k}$${\ displaystyle x_ {i}}$${\ displaystyle C_ {i}}$${\ displaystyle k}$${\ displaystyle P '}$${\ displaystyle A: = \ {x_ {1}, x_ {2}, \ dots, x_ {k} \}}$${\ displaystyle A}$${\ displaystyle A_ {i}}$${\ displaystyle k}$${\ displaystyle x_ {i}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A_ {i} \ cap C_ {j} \ neq \ emptyset}$${\ displaystyle y \ in A_ {i} \ cap C_ {j}}$${\ displaystyle y \ leq x_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {i} \ not \ geq x_ {j}}$${\ displaystyle x_ {i} \ not \ geq y}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle x_ {j} \ not \ geq x_ {i}}$${\ displaystyle A}$

Agora voltamos para . Suponha primeiro isso para alguns . Deixe ser a corrente . Então, pela escolha de , não tem uma antichain de tamanho . A indução, então, implica que pode ser coberta por cadeias disjuntas, uma vez que é uma anticadeia de tamanho em . Assim, podem ser cobertos por correntes disjuntas, conforme necessário. Em seguida, se para cada um , então é uma anticadeia de tamanho em (visto que é máximo em ). Agora pode ser coberto pelas correntes , completando a prova. ${\ displaystyle P}$${\ displaystyle a \ geq x_ {i}}$${\ displaystyle i \ in \ {1,2, \ dots, k \}}$${\ displaystyle K}$${\ displaystyle \ {a \} \ cup \ {z \ in C_ {i}: z \ leq x_ {i} \}}$${\ displaystyle x_ {i}}$${\ displaystyle P \ setminus K}$${\ displaystyle k}$${\ displaystyle P \ setminus K}$${\ displaystyle k-1}$${\ displaystyle A \ setminus \ {x_ {i} \}}$${\ displaystyle k-1}$${\ displaystyle P \ setminus K}$${\ displaystyle P}$${\ displaystyle k}$${\ displaystyle a \ not \ geq x_ {i}}$${\ displaystyle i \ in \ {1,2, \ dots, k \}}$${\ displaystyle A \ cup \ {a \}}$${\ displaystyle k + 1}$${\ displaystyle P}$${\ displaystyle a}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle k + 1}$${\ displaystyle \ {a \}, C_ {1}, C_ {2}, \ dots, C_ {k}}$

Prova via teorema de Kőnig

Prova do teorema de Dilworth via teorema de Kőnig: construção de um grafo bipartido de uma ordem parcial e particionamento em cadeias de acordo com uma correspondência

Como uma série de outros resultados em combinatória, o teorema de Dilworth é equivalente ao teorema de Kőnig sobre combinação de grafos bipartida e vários outros teoremas relacionados, incluindo o teorema do casamento de Hall ( Fulkerson 1956 ).

Para provar o teorema de Dilworth para uma ordem parcial S com n elementos, usando o teorema de Kőnig, defina um grafo bipartido G = ( U , V , E ) onde U = V = S e onde ( u , v ) é uma aresta em G quando u < v em S . Pelo teorema de Kőnig, existe um casamento M em G , e um conjunto de vértices C em G , tal que cada aresta no gráfico contém pelo menos um vértice em C e tal que M e C têm a mesma cardinalidade m . Seja A o conjunto de elementos de S que não correspondem a nenhum vértice em C ; então A tem pelo menos n - m elementos (possivelmente mais se C contiver vértices correspondentes ao mesmo elemento em ambos os lados da bipartição) e não há dois elementos de A comparáveis ​​entre si. Vamos P ser uma família de cadeias formadas pela inclusão de x e y na mesma cadeia, sempre que há uma aresta ( x , y ) em H ; então P tem cadeias n - m . Portanto, construímos uma anticadeia e uma partição em cadeias com a mesma cardinalidade.

Para provar o teorema de Kőnig a partir do teorema de Dilworth, para um grafo bipartido G = ( U , V , E ), forme uma ordem parcial nos vértices de G em que u < v exatamente quando u está em U , v está em V , e lá existe uma aresta em E de u a v . Pelo teorema de Dilworth, existe uma anticadeia A e uma partição em cadeias P, ambas com o mesmo tamanho. Mas as únicas cadeias não triviais na ordem parcial são pares de elementos correspondentes às arestas do gráfico, de modo que as cadeias não triviais em P formam uma correspondência no gráfico. O complemento de A forma uma cobertura de vértices em G com a mesma cardinalidade desta correspondência.

Essa conexão com o casamento bipartido permite que a largura de qualquer ordem parcial seja calculada em tempo polinomial . Mais precisamente, ordens parciais de n- elementos de largura k podem ser reconhecidas no tempo O ( kn ² ) ( Felsner, Raghavan & Spinrad 2003 ).

Extensão para infinitos conjuntos parcialmente ordenados

O teorema de Dilworth para conjuntos parcialmente ordenados infinitos afirma que um conjunto parcialmente ordenado tem largura finita w se e somente se ele pode ser particionado em cadeias w . Pois, suponha que uma ordem parcial infinita P tenha largura w , o que significa que há no máximo um número finito w de elementos em qualquer anticadeia. Para qualquer subconjunto S de P , uma decomposição em cadeias w (se houver) pode ser descrita como uma coloração do gráfico de incomparabilidade de S (um gráfico que tem os elementos de S como vértices, com uma aresta entre cada dois elementos incomparáveis) usando cores w ; cada classe de cor em uma coloração adequada do gráfico de incomparabilidade deve ser uma cadeia. Partindo do pressuposto de que P tem largura w , e pela versão finita do teorema de Dilworth, todo subconjunto finito S de P tem um gráfico de incomparabilidade w- colorível. Portanto, pelo teorema de De Bruijn-Erdős , o próprio P também tem um gráfico de incomparabilidade w- colorable e, portanto, tem a partição desejada em cadeias ( Harzheim 2005 ).

No entanto, o teorema não se estende tão simplesmente a conjuntos parcialmente ordenados nos quais a largura, e não apenas a cardinalidade do conjunto, é infinita. Nesse caso, o tamanho da maior anticadeia e o número mínimo de cadeias necessárias para cobrir o pedido parcial podem ser muito diferentes um do outro. Em particular, para cada número cardinal infinito κ, existe um conjunto infinito parcialmente ordenado de largura ℵ _0, cuja partição nas menores cadeias tem cadeias κ ( Harzheim 2005 ).

Perles (1963) discute análogos do teorema de Dilworth no cenário infinito.

Dual do teorema de Dilworth (teorema de Mirsky)

Um dual do teorema de Dilworth afirma que o tamanho da maior cadeia em uma ordem parcial (se finita) é igual ao menor número de antichains nas quais a ordem pode ser particionada ( Mirsky 1971 ). A prova disso é muito mais simples do que a prova do próprio teorema de Dilworth: para qualquer elemento x , considere as cadeias que têm x como seu maior elemento e deixe N ( x ) denotar o tamanho da maior dessas cadeias x- máximas. Então, cada conjunto N ⁻¹ ( i ), consistindo de elementos que têm valores iguais de N , é uma anticadeia, e essas anticadeias dividem a ordem parcial em um número de anticadeias igual ao tamanho da maior cadeia.

Perfeição dos gráficos de comparabilidade

Um gráfico de comparabilidade é um gráfico não direcionado formado a partir de uma ordem parcial, criando um vértice por elemento da ordem e uma aresta conectando quaisquer dois elementos comparáveis. Assim, um clique em um gráfico de comparabilidade corresponde a uma cadeia, e um conjunto independente em um gráfico de comparabilidade corresponde a uma anticadeia. Qualquer subgráfico induzido de um gráfico de comparabilidade é ele próprio um gráfico de comparabilidade, formado a partir da restrição da ordem parcial a um subconjunto de seus elementos.

Um gráfico não direcionado é perfeito se, em cada subgrafo induzido, o número cromático é igual ao tamanho do maior clique. Todo gráfico de comparabilidade é perfeito: este é essencialmente apenas o teorema de Mirsky, reformulado em termos da teoria dos grafos ( Berge & Chvátal 1984 ). Pelo teorema do gráfico perfeito de Lovász (1972) , o complemento de qualquer gráfico perfeito também é perfeito. Portanto, o complemento de qualquer gráfico de comparabilidade é perfeito; trata-se essencialmente do próprio teorema de Dilworth, reafirmado em termos da teoria dos grafos ( Berge & Chvátal 1984 ). Assim, a propriedade de complementação de grafos perfeitos pode fornecer uma prova alternativa do teorema de Dilworth.

Largura de pedidos parciais especiais

A rede booleana B _n é o conjunto de potência de um conjunto de n- elementos X —essencialmente {1, 2,…, n } —ordenado por inclusão ou, notacionalmente, (2 ^{[ n ]} , ⊆). O teorema de Sperner afirma que uma antichain máxima de B _n tem tamanho no máximo

${\ displaystyle \ operatorname {largura} (B_ {n}) = {n \ escolher \ lfloor {n / 2} \ rfloor}.}$

Em outras palavras, uma maior família de subconjuntos incomparáveis ​​de X é obtida selecionando os subconjuntos de X que têm tamanho mediano. A desigualdade de Lubell-Yamamoto-Meshalkin também diz respeito a antichains em um conjunto de potência e pode ser usada para provar o teorema de Sperner.

Se ordenarmos os inteiros no intervalo [1, 2 n ] por divisibilidade , o subintervalo [ n  + 1, 2 n ] forma uma anticadeia com cardinalidade n . Uma partição dessa ordem parcial em n cadeias é fácil de conseguir: para cada número inteiro ímpar m em [1,2 n ], forme uma cadeia de números na forma m 2 ⁱ . Portanto, pelo teorema de Dilworth, a largura dessa ordem parcial é n .

O teorema de Erdős – Szekeres em subsequências monótonas pode ser interpretado como uma aplicação do teorema de Dilworth para ordens parciais de dimensão de ordem dois ( Steele 1995 ).

A "dimensão convexa" de um antimatróide é definida como o número mínimo de cadeias necessárias para definir o antimatróide, e o teorema de Dilworth pode ser usado para mostrar que é igual à largura de uma ordem parcial associada; esta conexão leva a um algoritmo de tempo polinomial para dimensão convexa ( Edelman & Saks 1988 ).

Referências

• Berge, Claude ; Chvátal, Václav (1984), Topics on Perfect Graphs , Annals of Discrete Mathematics, 21 , Elsevier, p. viii, ISBN 978-0-444-86587-8
• Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics , 51 (1): 161-166, doi : 10.2307 / 1969503 , JSTOR  1969503.
• Edelman, Paul H .; Saks, Michael E. (1988), "Representação combinatória e dimensão convexa de geometrias convexas", Ordem , 5 (1): 23-32, doi : 10.1007 / BF00143895 , S2CID  119826035.
• Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Recognition algoritms for orders of small width and graphs of small Dilworth number" , Order , 20 (4): 351–364 (2004), doi : 10.1023 / B: ORDE.0000034609.99940.fb , MR  2079151 , S2CID  1363140.
• Fulkerson, DR (1956), "Nota sobre o teorema de decomposição de Dilworth para conjuntos parcialmente ordenados", Proceedings of the American Mathematical Society , 7 (4): 701–702, doi : 10.2307 / 2033375 , JSTOR  2033375.
• Galvin, Fred (1994), "Uma prova do teorema da decomposição em cadeia de Dilworth", The American Mathematical Monthly , 101 (4): 352-353, doi : 10.2307 / 2975628 , JSTOR  2975628 , MR  1270960.
• Greene, Curtis ; Kleitman, Daniel J. (1976), "The structure of Sperner -families", Journal of Combinatorial Theory , Series A , 20 (1): 41-68, doi : 10.1016 / 0097-3165 (76) 90077-7${\ displaystyle k}$.
• Harzheim, Egbert (2005), conjuntos ordenados , Advances in Mathematics (Springer), 7 , New York: Springer, Theorem 5.6, p. 60, ISBN 0-387-24219-8, MR  2127991.
• Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics , 2 (3): 253–267, doi : 10.1016 / 0012-365X (72) 90006-4.
• Mirsky, Leon (1971), "Um dual do teorema de decomposição de Dilworth", American Mathematical Monthly , 78 (8): 876-877, doi : 10.2307 / 2316481 , JSTOR  2316481.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Teorema 3.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Heidelberg: Springer, p. 42, doi : 10.1007 / 978-3-642-27875-4 , hdl : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR  2920058.
• Perles, Micha A. (1963), "On Dilworth's teorema no caso infinito", Israel Journal of Mathematics , 1 (2): 108-109, doi : 10.1007 / BF02759806 , MR  0168497 , S2CID  120943065.
• Steele, J. Michael (1995), "Variações sobre o tema da subsequência monótona de Erdős e Szekeres", em Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (eds.), Discrete Probability and Algorithms (PDF) , IMA Volumes in Mathematics and its Applications, 72 , Springer-Verlag, pp. 111–131.

links externos

• Equivalência de sete teoremas principais em combinatória
• "Dual of Dilworth's Theorem" , PlanetMath , arquivado do original em 2007-07-14
• Babai, László (2005), Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF) , arquivado do original (PDF) em 2011-07-20
• Felsner, S .; Raghavan, V. & Spinrad, J. (1999), Recognition Algorithms for Orders of Small Width e Graphs of Small Dilworth Number
• Weisstein, Eric W. "Dilworth's Lemma" . MathWorld .