En matemáticas , en las áreas de teoría del orden y combinatoria , el teorema de Dilworth caracteriza el ancho de cualquier conjunto finito parcialmente ordenado en términos de una partición del orden en un número mínimo de cadenas . Lleva el nombre del matemático Robert P. Dilworth (1950).
Una anticadena en un conjunto parcialmente ordenado es un conjunto de elementos de los cuales dos no son comparables entre sí, y una cadena es un conjunto de elementos de los cuales dos son comparables. 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 finito parcialmente ordenado, la anticadena más grande tiene el mismo tamaño que la descomposición de la 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 de la cadena es su número de cadenas. El ancho del orden parcial se define como el tamaño común de la descomposición de la anticadena y la cadena.
Una versión del teorema para conjuntos infinitos parcialmente ordenados establece que, cuando existe una descomposición en un número finito de cadenas, o cuando existe un límite superior finito en el tamaño de una anticadena, los tamaños de la anticadena más grande y de la descomposición de la cadena más pequeña vuelven a ser iguales.
La siguiente prueba por inducción sobre el tamaño del conjunto parcialmente ordenado se basa en la de Galvin (1994).
Sea un conjunto finito parcialmente ordenado. El teorema se cumple trivialmente si está vacío. Entonces, supongamos que tiene al menos un elemento y sea un elemento máximo de .
Por inducción, suponemos que para algún número entero el conjunto parcialmente ordenado puede estar cubierto por cadenas disjuntas y tiene al menos una anticadena de tamaño . Claramente, para . Para , sea el elemento máximo en que pertenece a una anticadena de tamaño en y conjunto . Afirmamos que es una anticadena. Sea una anticadena de tamaño que contenga . Fijar índices distintos arbitrarios y . Entonces . Dejar . Entonces , por la definición de . Esto implica que , desde . Al intercambiar los roles de y en este argumento también tenemos . Esto verifica que es una anticadena.
Ahora volvemos a . Supongamos primero que para algunos . Sea la cadena . Entonces por elección de , no tiene anticadena de tamaño . La inducción implica entonces que puede estar cubierto por cadenas disjuntas ya que es una anticadena de tamaño en . Por tanto, pueden cubrirse mediante cadenas disjuntas, según sea necesario. A continuación, si es para cada uno , entonces hay una anticadena de tamaño en (ya que es máxima en ). Ahora podemos quedar cubiertos por las cadenas , completando la prueba.
Como muchos otros resultados en combinatoria, el teorema de Dilworth es equivalente al teorema de Kőnig sobre coincidencia de grafos bipartitos y varios otros teoremas relacionados, incluido el teorema del matrimonio de Hall (Fulkerson 1956).
Para demostrar el teorema de Dilworth para un orden parcial S con n elementos, utilizando el teorema de Kőnig, defina un gráfico bipartito G = ( U , V , E ) donde U = V = S y donde ( u , v ) es una arista en G cuando u < v en S . Según el teorema de Kőnig, existe una coincidencia M en G y un conjunto de vértices C en G , tal que cada arista del gráfico 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 correspondientes 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 xey en la misma cadena siempre que haya una arista ( x , y ) en M ; entonces P tiene n - m cadenas. Por tanto, hemos construido una anticadena y una partición en cadenas con la misma cardinalidad.
Para probar el teorema de Kőnig a partir del teorema de Dilworth, para un gráfico bipartito G = ( U , V , E ), forme un orden parcial en los vértices de G en el que u < v exactamente cuando u está en U , v está en V , y allí Existe una arista en E de u a v . Según el teorema de Dilworth, existe una anticadena A y una partición en cadenas P , las cuales tienen el mismo tamaño. Pero las únicas cadenas no triviales en el orden parcial son pares de elementos correspondientes a los bordes del gráfico, por lo que las cadenas no triviales en P forman una coincidencia en el gráfico. El complemento de A forma una cobertura de vértice en G con la misma cardinalidad que esta coincidencia.
Esta conexión con la coincidencia bipartita permite calcular el ancho de cualquier orden parcial en tiempo polinómico . Más precisamente, los órdenes parciales de n elementos de ancho k pueden reconocerse en el tiempo O ( kn 2 ) (Felsner, Raghavan y Spinrad 2003).
El teorema de Dilworth para infinitos conjuntos parcialmente ordenados establece que un conjunto parcialmente ordenado tiene un ancho finito w si y sólo si puede dividirse en w cadenas. Porque, supongamos que un orden parcial 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 gráfico de incomparabilidad de S (un gráfico que tiene los elementos de S como vértices, con un borde entre cada dos elementos incomparables) usando w colores; Cada clase de color en una coloración adecuada del gráfico de incomparabilidad debe ser una cadena. Según el supuesto de que P tiene ancho w , y según la versión finita del teorema de Dilworth, cada subconjunto finito S de P tiene un gráfico de incomparabilidad w -coloreable. Por lo tanto, según el teorema de De Bruijn-Erdős , P en sí también tiene un gráfico de incomparabilidad w -colorable y, por lo tanto, tiene la partición deseada en cadenas (Harzheim 2005).
Sin embargo, el teorema no se extiende tan simplemente a conjuntos parcialmente ordenados en los que la anchura, y no sólo la cardinalidad del conjunto, es infinita. En este caso, el tamaño de la anticadena más grande y el número mínimo de cadenas necesarias para cubrir el pedido parcial pueden ser muy diferentes entre sí. En particular, para cada número cardinal infinito κ existe un conjunto infinito parcialmente ordenado de ancho ℵ 0 cuya partición en la menor cantidad de cadenas tiene κ cadenas (Harzheim 2005).
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 dividir el orden (Mirsky 1971). La prueba de esto es mucho más simple que la prueba del propio teorema de Dilworth: para cualquier elemento x , considere las cadenas que tienen x como su elemento más grande, y sea N ( x ) el tamaño de la mayor de estas x -cadenas máximas. Entonces cada conjunto N −1 ( i ), que consta de elementos que tienen valores iguales de N , es una anticadena, y estas anticadenas dividen el orden parcial en un número de anticadenas igual al tamaño de la cadena más grande.
Un gráfico de comparabilidad es un gráfico no dirigido formado a partir de un orden parcial mediante la creación de un vértice por elemento del orden y un borde que conecta dos elementos comparables cualesquiera. Así, una camarilla en un gráfico de comparabilidad corresponde a una cadena, y un conjunto independiente en un gráfico de comparabilidad corresponde a una anticadena. Cualquier subgrafo inducido de un gráfico de comparabilidad es en sí mismo un gráfico de comparabilidad, formado a partir de la restricción del orden parcial a un subconjunto de sus elementos.
Un gráfico no dirigido es perfecto si, en cada subgrafo inducido, el número cromático es igual al tamaño de la camarilla más grande. Todo gráfico de comparabilidad es perfecto: esto es esencialmente sólo el teorema de Mirsky, reformulado en términos de teoría de grafos (Berge y Chvátal 1984). Según el teorema del grafo perfecto de Lovász (1972), el complemento de cualquier grafo perfecto también es perfecto. Por tanto, el complemento de cualquier gráfico de comparabilidad es perfecto; esto es esencialmente el propio teorema de Dilworth, reformulado en términos de teoría de grafos (Berge y Chvátal 1984). Por tanto, la propiedad de complementación de los gráficos perfectos puede proporcionar una prueba alternativa del teorema de Dilworth.
La red booleana B n es el conjunto potencia de un conjunto de n elementos X , 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 como máximo
En otras palabras, se obtiene una familia más grande de subconjuntos incomparables de X seleccionando los subconjuntos de X que tienen tamaño mediano. La desigualdad de Lubell-Yamamoto-Meshalkin también afecta a las anticadenas en un conjunto de potencias y puede usarse para demostrar el teorema de Sperner.
Si ordenamos los números enteros en el intervalo [1, 2 n ] por divisibilidad , el subintervalo [ n + 1, 2 n ] forma una anticadena con cardinalidad n . Una partición de este orden parcial en n cadenas es fácil de lograr: para cada entero impar m en [1,2 n ], forme una cadena de números de la forma m 2 i . 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 orden dimensión dos (Steele 1995).
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 se puede utilizar para demostrar que es igual al ancho de un orden parcial asociado; esta conexión conduce a un algoritmo de tiempo polinomial para dimensión convexa (Edelman y Saks 1988).
