Teorema de Dilworth

En matemáticas , en las áreas de teoría del orden y combinatoria , el teorema de Dilworth establece que, en cualquier conjunto finito parcialmente ordenado , el tamaño máximo de una anticadena de elementos incomparables es igual al número mínimo de cadenas necesarias para cubrir todos los elementos. Este número se denomina ancho del orden parcial. El teorema recibe su nombre del matemático Robert P. Dilworth , quien lo publicó en 1950. ^{[ 1 ]}

Una versión del teorema para conjuntos parcialmente ordenados infinitos establece que, cuando existe una descomposición en un número finito de cadenas, o cuando existe un límite superior finito para el tamaño de una anticadena, los tamaños de la anticadena más grande y de la descomposición en cadena más pequeña son nuevamente iguales.

En un conjunto parcialmente ordenado, una anticadena es un conjunto cuyos elementos no son comparables entre sí, y una cadena es un conjunto cuyos elementos son comparables entre sí. Una descomposición en cadena es una partición de los elementos del orden en cadenas disjuntas . El teorema de Dilworth establece que, en cualquier conjunto parcialmente ordenado finito, la anticadena más grande tiene el mismo tamaño que la descomposición en cadena más pequeña. Aquí, el tamaño de la anticadena es su número de elementos, y el tamaño de la descomposición en cadena es su número de cadenas. La anchura del orden parcial se define como el tamaño común de la anticadena y la descomposición en cadena.

La siguiente demostración por inducción sobre el tamaño del conjunto parcialmente ordenado${\displaystyle P}$se basa en el de Galvin ( 1994 ) . 

Dejar${\displaystyle P}$Sea un conjunto parcialmente ordenado finito. El teorema se cumple trivialmente si${\displaystyle P}$está vacío. Entonces, supongamos que${\displaystyle P}$tiene al menos un elemento, y deje que${\displaystyle a}$ser un elemento máximo de${\displaystyle P}$.

Por inducción, suponemos que para algún entero${\displaystyle k}$el conjunto parcialmente ordenado${\displaystyle P':=P\setminus \{a\}}$puede estar cubierto por${\displaystyle k}$cadenas disjuntas${\displaystyle C_{1},\dots ,C_{k}}$y tiene al menos una anticadena${\displaystyle A_{0}}$de tamaño${\displaystyle k}$. Claramente,${\displaystyle A_{0}\cap C_{i}\neq \emptyset }$para${\displaystyle i=1,2,\dots ,k}$. Para${\displaystyle i=1,2,\dots ,k}$, dejar${\displaystyle x_{i}}$ser el elemento máximo en${\displaystyle C_{i}}$que pertenece a una anticadena de tamaño${\displaystyle k}$en${\displaystyle P'}$y establecer${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$Afirmamos que${\displaystyle A}$es una anticadena. Dejemos${\displaystyle A_{i}}$ser una anticadena de tamaño${\displaystyle k}$que contiene${\displaystyle x_{i}}$. Fijar índices distintos arbitrarios${\displaystyle i}$y${\displaystyle j}$. Entonces${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$. Dejar${\displaystyle y\in A_{i}\cap C_{j}}$. Entonces${\displaystyle y\leq x_{j}}$, por definición de${\displaystyle x_{j}}$Esto implica que${\displaystyle x_{i}\not \geq x_{j}}$, desde${\displaystyle x_{i}\not \geq y}$. Al intercambiar los roles de${\displaystyle i}$y${\displaystyle j}$en este argumento también tenemos${\displaystyle x_{j}\not \geq x_{i}}$Esto verifica que${\displaystyle A}$es una anticadena.

Ahora volvemos a${\displaystyle P}$Supongamos primero que${\displaystyle a\geq x_{i}}$para algunos${\displaystyle i\in \{1,2,\dots ,k\}}$. Dejar${\displaystyle K}$ser la cadena${\displaystyle \{a\}\cup \{z\in C_{i}:z\leq x_{i}\}}$. Luego, por elección de${\displaystyle x_{i}}$,${\displaystyle P\setminus K}$no tiene una anticadena de tamaño${\displaystyle k}$La inducción implica entonces que${\displaystyle P\setminus K}$puede estar cubierto por${\displaystyle k-1}$cadenas disjuntas desde${\displaystyle A\setminus \{x_{i}\}}$es una anticadena de tamaño${\displaystyle k-1}$en${\displaystyle P\setminus K}$. De este modo,${\displaystyle P}$puede estar cubierto por${\displaystyle k}$cadenas disjuntas, según sea necesario. A continuación, si${\displaystyle a\not \geq x_{i}}$para cada${\displaystyle i\in \{1,2,\dots ,k\}}$, entonces${\displaystyle A\cup \{a\}}$es una anticadena de tamaño${\displaystyle k+1}$en${\displaystyle P}$(desde${\displaystyle a}$es máximo en${\displaystyle P}$). Ahora${\displaystyle P}$puede estar cubierto por el${\displaystyle k+1}$cadenas${\displaystyle \{a\},C_{1},C_{2},\dots ,C_{k}}$, completando la prueba.

Al igual que otros resultados en combinatoria, el teorema de Dilworth es equivalente al teorema de Kőnig sobre el emparejamiento de grafos bipartitos y a otros teoremas relacionados, incluido el teorema de matrimonio de Hall . ^{[ 2 ]}

Para demostrar el teorema de Dilworth para un orden parcial S con n elementos, usando el teorema de Kőnig, definamos un grafo bipartito G = ( U , V , E ) donde U = V = S y donde ( u , v ) es una arista en G cuando u < v en S . Por el teorema de Kőnig, existe un emparejamiento M en G , y un conjunto de vértices C en G , tal que cada arista en el grafo contiene al menos un vértice en C y tal que M y C tienen la misma cardinalidad m . Sea A el conjunto de elementos de S que no corresponden a ningún vértice en C ; entonces A tiene al menos n - m elementos (posiblemente más si C contiene vértices que corresponden al mismo elemento en ambos lados de la bipartición) y no hay dos elementos de A que sean comparables entre sí. Sea P una familia de cadenas formada al incluir x e y en la misma cadena siempre que haya una arista ( x , y ) en M ; Entonces P tiene n - m cadenas. Por lo tanto, hemos construido una anticadena y una partición en cadenas con la misma cardinalidad.

Para demostrar el teorema de Kőnig a partir del teorema de Dilworth, para un grafo bipartito G = ( U , V , E ), forme un orden parcial en los vértices de G tal que u < v exactamente cuando u está en U , v está en V y existe una arista en E de u a v . Por el teorema de Dilworth, existe una anticadena A y una partición en cadenas P, ambas del mismo tamaño. Pero las únicas cadenas no triviales en el orden parcial son pares de elementos que corresponden a las aristas del grafo, por lo que las cadenas no triviales en P forman un emparejamiento en el grafo. El complemento de A forma una cobertura de vértices en G con la misma cardinalidad que este emparejamiento.

^{Esta conexión con el} emparejamiento bipartito permite calcular el ancho de cualquier orden parcial en tiempo polinomial . Más precisamente, los órdenes parciales de n elementos de ancho k pueden reconocerse en tiempo O ( kn² ). ^{[ 3 ]}

El teorema de Dilworth para conjuntos parcialmente ordenados infinitos establece que un conjunto parcialmente ordenado tiene ancho finito w si y solo si puede particionarse en w cadenas. Supongamos que un conjunto parcialmente ordenado infinito P tiene ancho w , lo que significa que hay como máximo un número finito w de elementos en cualquier anticadena. Para cualquier subconjunto S de P , una descomposición en w cadenas (si existe) puede describirse como una coloración del grafo de incomparabilidad de S (un grafo que tiene los elementos de S como vértices, con una arista entre cada dos elementos incomparables) usando w colores; cada clase de color en una coloración propia del grafo de incomparabilidad debe ser una cadena. Bajo la suposición de que P tiene ancho w , y por la versión finita del teorema de Dilworth, todo subconjunto finito S de P tiene un grafo de incomparabilidad w -coloreable. Por lo tanto, por el teorema de De Bruijn-Erdős , P mismo también tiene un grafo de incomparabilidad w -coloreable, y por lo tanto tiene la partición deseada en cadenas. ^{[ 4 ]}

Sin embargo, el teorema no se extiende tan fácilmente a conjuntos parcialmente ordenados en los que el ancho, y no solo la cardinalidad del conjunto, es infinito. En este caso, el tamaño de la anticadena más grande y el número mínimo de cadenas necesarias para cubrir el orden parcial pueden ser muy diferentes entre sí. En particular, para cada número cardinal infinito κ existe un conjunto parcialmente ordenado infinito de ancho ℵ ₀ cuya partición en el menor número de cadenas tiene κ cadenas. ^{[ 4 ]}

Perles (1963) analiza análogos del teorema de Dilworth en el contexto infinito.

Un dual del teorema de Dilworth establece que el tamaño de la cadena más grande en un orden parcial (si es finito) es igual al número más pequeño de anticadenas en las que se puede particionar el orden. ^{[ 5 ]} Esto se llama teorema de Mirsky . Su demostración es mucho más simple que la demostración del teorema de Dilworth: para cualquier elemento x , consideremos las cadenas que tienen a x como su elemento más grande, y sea N ( x ) el tamaño de la más grande de estas cadenas x -maximales. Entonces, cada conjunto N ⁻¹ ( i ), que consta de elementos que tienen valores iguales de N , es una anticadena, y estas anticadenas particionan el orden parcial en un número de anticadenas igual al tamaño de la cadena más grande.

Un grafo de comparabilidad es un grafo no dirigido formado a partir de un orden parcial mediante la creación de un vértice por cada elemento del orden y una arista que conecta dos elementos comparables cualesquiera. Así, una camarilla en un grafo de comparabilidad corresponde a una cadena, y un conjunto independiente corresponde a una anticadena. Cualquier subgrafo inducido de un grafo de comparabilidad es, a su vez, un grafo de comparabilidad, formado a partir de la restricción del orden parcial a un subconjunto de sus elementos.

Un grafo no dirigido es perfecto si, en cada subgrafo inducido, el número cromático es igual al tamaño de la mayor camarilla. Todo grafo de comparabilidad es perfecto: esto es esencialmente el teorema de Mirsky, reformulado en términos de teoría de grafos. ^{[ 6 ]} Según el teorema del grafo perfecto de Lovász (1972) , el complemento de cualquier grafo perfecto también es perfecto. Por lo tanto, el complemento de cualquier grafo de comparabilidad es perfecto; esto es esencialmente el teorema de Dilworth, reformulado en términos de teoría de grafos ( Berge y Chvátal 1984 ) . Así, la propiedad de complementación de los grafos perfectos puede proporcionar una demostración alternativa del teorema de Dilworth.

El retículo booleano B _n es el conjunto potencia de un conjunto X de n elementos —esencialmente {1, 2, …, n }— ordenado por inclusión o, notación, (2 ^{[ n ]} , ⊆). El teorema de Sperner establece que una anticadena máxima de B _n tiene un tamaño máximo de n elementos.

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

En otras palabras, la familia más grande de subconjuntos incomparables de X se obtiene seleccionando los subconjuntos de X que tienen un tamaño mediano. La desigualdad de Lubell-Yamamoto-Meshalkin también se refiere a anticadenas en un conjunto potencia y puede usarse para demostrar el teorema de Sperner.

Si ordenamos los enteros en el intervalo [1,  2 n ] por divisibilidad , el subintervalo [ n  +  1,  2 n ] forma una anticadena con cardinalidad n . Es fácil lograr una partición de este orden parcial en n cadenas: para cada entero impar m en [1,2 n ], se forma una cadena de los números de la forma m 2 ⁱ . Por lo tanto, según el teorema de Dilworth, el ancho de este orden parcial es n .

El teorema de Erdős-Szekeres sobre subsecuencias monótonas puede interpretarse como una aplicación del teorema de Dilworth a órdenes parciales de dimensión dos. ^{[ 7 ]}

La "dimensión convexa" de un antimatroide se define como el número mínimo de cadenas necesarias para definir el antimatroide, y el teorema de Dilworth puede utilizarse para demostrar que es igual al ancho de un orden parcial asociado; esta conexión conduce a un algoritmo de tiempo polinomial para la dimensión convexa. ^{[ 8 ]}

• Berge, Claude ; Chvátal, Václav (1984), Temas sobre grafos perfectos , Anales de Matemáticas Discretas, vol.  21, Elsevier, pág.  viii, ISBN 978-0-444-86587-8
• Dilworth, Robert P. (1950), "Un teorema de descomposición para conjuntos parcialmente ordenados", Annals of Mathematics , 51 (1): 161– 166, doi : 10.2307/1969503 , JSTOR 1969503 .
• Edelman, Paul H.; Saks, Michael E. (1988), "Representación combinatoria y dimensión convexa de geometrías convexas", Order , 5 (1): 23– 32, doi : 10.1007/BF00143895 , S2CID 119826035 .
• Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos de reconocimiento para órdenes de ancho pequeño y grafos de número de Dilworth pequeño" , Order , 20 (4): 351–364 (2004), doi : 10.1023/B:ORDE.0000034609.99940.fb , MR 2079151 , S2CID 1363140  .
• Fulkerson, DR (1956), "Nota sobre el teorema de descomposición de Dilworth para conjuntos parcialmente ordenados", Actas de la Sociedad Matemática Americana , 7 (4): 701– 702, doi : 10.2307/2033375 , JSTOR 2033375 .
• Galvin, Fred (1994), "Una demostración del teorema de descomposición en cadena de Dilworth", The American Mathematical Monthly , 101 (4): 352– 353, doi : 10.2307/2975628 , JSTOR 2975628 , MR 1270960  .
• Greene, Curtis ; Kleitman, Daniel J. (1976), "La estructura de Sperner${\displaystyle k}$-familias", Journal of Combinatorial Theory, Serie A , 20 (1): 41– 68, doi : 10.1016/0097-3165(76)90077-7.
• Harzheim, Egbert (2005), Conjuntos ordenados , Advances in Mathematics (Springer), vol.  7, Nueva York: Springer, Teorema  5.6, pág.  60, ISBN 0-387-24219-8, MR 2127991 .
• Lovász, László (1972), "Hipergrafos normales y la conjetura del grafo perfecto", Matemáticas Discretas , 2 (3): 253– 267, doi : 10.1016/0012-365X(72)90006-4.
• Mirsky, Leon (1971), "Un dual del teorema de descomposición de Dilworth", American Mathematical Monthly , 78 (8): 876– 877, doi : 10.2307/2316481 , JSTOR 2316481 .
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Teorema 3.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol.  28, Heidelberg: Springer, p.  42, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058 .
• Perles, Micha A. (1963), "Sobre el teorema de Dilworth en el caso infinito", Israel Journal of Mathematics , 1 (2): 108– 109, doi : 10.1007/BF02759806 , MR 0168497 , S2CID 120943065  .
• Steele, J. Michael (1995), "Variaciones sobre el tema de la subsecuencia monótona de Erdős y Szekeres", en Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et  al. (eds.), Discrete Probability and Algorithms (PDF) , IMA Volumes in Mathematics and its Applications, vol.  72, Springer-Verlag, pp . 111–131 .

• Robert D. Borgersen (26 de noviembre de 2004), Equivalencia de siete teoremas principales en combinatoria (PDF) , archivado del original (PDF) el 21 de julio de 2011.
• Dual del teorema de Dilworth en PlanetMath .
• Babai, László (2005), Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF) , archivado del original (PDF) el 20 de julio de 2011.
• Felsner, S.; Raghavan, V. y Spinrad, J. (1999), Algoritmos de reconocimiento para órdenes de ancho pequeño y grafos de número de Dilworth pequeño
• Weisstein, Eric W. "El lema de Dilworth" . MathWorld .