En matemáticas , en las áreas de teoría de órdenes 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 ).
Un antichain en un conjunto parcialmente ordenado es un conjunto de elementos de los cuales no hay dos comparables entre sí, y una cadena es un conjunto de elementos cada dos de los cuales son comparables. Una descomposición en cadena es una partición de los elementos del orden en cadenas separadas . El teorema de Dilworth establece que, en cualquier conjunto finito parcialmente ordenado, el antichain más grande tiene el mismo tamaño que la descomposición de la cadena más pequeña. Aquí, el tamaño del antichain 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 del antichain y la descomposición de la cadena.
Una versión del teorema para infinitos conjuntos 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 un antichain, los tamaños del antichain más grande y de la descomposición de la cadena más pequeña son de nuevo iguales.
Prueba inductiva
La siguiente prueba por inducción sobre el tamaño del conjunto parcialmente ordenado se basa en el de Galvin ( 1994 ).
Dejar ser un conjunto finito parcialmente ordenado. El teorema es trivial siesta vacio. Entonces, asuma que tiene al menos un elemento, y deja ser un elemento máximo de .
Por inducción, asumimos que para algún número entero el conjunto parcialmente ordenado puede ser cubierto por cadenas disjuntas y tiene al menos un antichain de tamaño . Claramente, por . Para, dejar ser el elemento máximo en que pertenece a un antichain de tamaño en , y establecer . Afirmamos quees un antichain. Dejar ser un antichain de tamaño eso contiene . Corregir índices distintos arbitrarios y . Luego. Dejar. Luego, por la definición de . Esto implica que, desde . Intercambiando los roles de y en este argumento también tenemos . Esto verifica que es un antichain.
Ahora volvemos a . Supongamos primero que para algunos . Dejar ser la cadena . Luego, por la eleccin de, no tiene un antichain de tamaño . La inducción implica entonces que puede ser cubierto por cadenas disjuntas desde es un antichain de tamaño en . Por lo tanto, puede ser cubierto por cadenas disjuntas, según sea necesario. Siguiente, si para cada , luego es un antichain de tamaño en (desde es máximo en ). Ahora puede ser cubierto por el cadenas , completando la prueba.
Demostración mediante el teorema de Kőnig
Como una serie de otros resultados en combinatoria, el teorema de Dilworth es equivalente al teorema de Kőnig sobre la 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, usando 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 , de modo que cada borde en el 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 comparables entre sí. Deje que P sea una familia de cadenas formadas mediante la inclusión de x y y en la misma cadena cada vez que hay un borde ( x , y ) en M ; entonces P tiene n - m cadenas. Por tanto, hemos construido un antichain 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 grafo 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 hay existe una arista en E de u a v . Según el teorema de Dilworth, existe un antichain 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 en el gráfico, por lo que las cadenas no triviales en P forman una coincidencia en el gráfico. El complemento de A forma una cubierta 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 polinomial . Más precisamente, los órdenes parciales de n elementos de ancho k pueden reconocerse en el tiempo O ( kn 2 ) ( Felsner, Raghavan & Spinrad 2003 ).
Extensión a infinitos conjuntos parcialmente ordenados
El teorema de Dilworth para infinitos conjuntos parcialmente ordenados establece que un conjunto parcialmente ordenado tiene un ancho finito w si y solo si puede dividirse en w cadenas. Porque, suponga 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 antichain. 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. Suponiendo que P tiene ancho w , y por la versión finita del teorema de Dilworth, cada subconjunto finito S de P tiene un gráfico de incomparabilidad w -colorable. Por lo tanto, según el teorema de De Bruijn-Erdős , P mismo 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 el ancho, y no solo la cardinalidad del conjunto, es infinito. En este caso, el tamaño del antichain 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 κ hay un conjunto infinito parcialmente ordenado de ancho ℵ 0 cuya partición en la menor cantidad de cadenas tiene cadenas κ ( Harzheim 2005 ).
Perles (1963) analiza los análogos del teorema de Dilworth en el escenario infinito.
Dual del teorema de Dilworth (teorema de Mirsky)
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 antichains en los que se puede dividir el orden ( Mirsky 1971 ). La prueba de esto es mucho más simple que la prueba del teorema de Dilworth en sí: 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 un antichain, y estos antichains dividen el orden parcial en un número de antichains igual al tamaño de la cadena más grande.
Perfección de gráficos de comparabilidad
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. Por lo tanto, una camarilla en un gráfico de comparabilidad corresponde a una cadena, y un conjunto independiente en un gráfico de comparabilidad corresponde a un antichain. Cualquier subgráfico 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 subgráfico inducido, el número cromático es igual al tamaño de la camarilla más grande. Cada gráfico de comparabilidad es perfecto: esto es esencialmente el teorema de Mirsky, reformulado en términos de la teoría de los gráficos ( Berge y Chvátal 1984 ). Según el teorema del gráfico perfecto de Lovász (1972) , el complemento de cualquier gráfico perfecto también es perfecto. Por tanto, el complemento de cualquier gráfico de comparabilidad es perfecto; esto es esencialmente el teorema de Dilworth en sí mismo, 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.
Ancho de pedidos parciales especiales
El retículo booleano B n es el conjunto de potencias de un conjunto de n elementos X —esencialmente {1, 2,…, n } —ordenados por inclusión o, notationally, (2 [ n ] , ⊆). El teorema de Sperner establece que un antichain máximo 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 un tamaño mediano. La desigualdad de Lubell-Yamamoto-Meshalkin también se refiere a antichains en un conjunto de potencias y puede usarse para probar el teorema de Sperner.
Si ordenamos los enteros en el intervalo [1, 2 n ] por divisibilidad , el subintervalo [ n + 1, 2 n ] forma un antichain 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 puede usarse 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 ( Edelman y Saks 1988 ).
Referencias
- Berge, Claude ; Chvátal, Václav (1984), Temas sobre gráficos perfectos , Annals of Discrete Mathematics, 21 , Elsevier, p. 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", Orden , 5 (1): 23–32, doi : 10.1007 / BF00143895 , S2CID 119826035.
- Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos de reconocimiento para órdenes de pequeño ancho y gráficos de pequeño número de Dilworth" , 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", Proceedings of the American Mathematical Society , 7 (4): 701–702, doi : 10.2307 / 2033375 , JSTOR 2033375.
- Galvin, Fred (1994), "Una prueba 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-families ", J. Combin. Theory Ser. A , 20 (1): 41–68, doi : 10.1016 / 0097-3165 (76) 90077-7.
- Harzheim, Egbert (2005), Conjuntos ordenados , Advances in Mathematics (Springer), 7 , Nueva York: Springer, Teorema 5.6, p. 60, ISBN 0-387-24219-8, MR 2127991.
- Lovász, László (1972), "Hipergrafías normales y la conjetura de la gráfica perfecta", Matemáticas discretas , 2 (3): 253-267, doi : 10.1016 / 0012-365X (72) 90006-4.
- Mirsky, Leon (1971), "Un teorema de descomposición dual 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", Esparcimiento: Gráficos, Estructuras y Algoritmos , Algoritmos y Combinatoria, 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), "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.), Probabilidad discreta y algoritmos (PDF) , Volúmenes IMA en matemáticas y sus aplicaciones, 72 , Springer-Verlag, págs. 111-131.
enlaces externos
- Equivalencia de siete teoremas principales en combinatoria
- "Dual of Dilworth's Theorem" , PlanetMath , archivado desde el original el 14 de julio de 2007
- Babai, László (2005), Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF) , archivado desde el original (PDF) en 2011-07-20
- Felsner, S .; Raghavan, V. y Spinrad, J. (1999), algoritmos de reconocimiento para órdenes de pequeño ancho y gráficos de pequeño número de Dilworth
- Weisstein, Eric W. "El lema de Dilworth" . MathWorld .