Teorema de Dilworth

El teorema de Dilworth  es una declaración combinatoria que caracteriza una propiedad extrema para los posets : un poset finito se puede dividir en cadenas separadas por pares , donde  es el número de elementos de la anticadena más grande del conjunto [1] (también llamado el ancho del poset) .

Una versión del teorema para posets infinitos: un poset tiene un ancho finito si y solo si se puede dividir en cadenas, pero no menos.

Lo demostró el matemático estadounidense Robert P. Dilworth ( 1914-1993), cuya principal área de investigación fue la teoría de la red . 

Prueba por inducción

La demostración por inducción sobre el tamaño de un poset se basa en la demostración de Galvin [2] .

Sea  un conjunto finito parcialmente ordenado. La declaración es trivial si está vacía. Así que suponga que tiene al menos un elemento, y  sea el elemento máximo de .

Por la hipótesis de inducción, para algún entero , un poset puede estar cubierto por cadenas disjuntas y tiene al menos una anticadena de tamaño . Está claro que para . Pues sea ,  el elemento máximo en , que pertenece a la anticadena de tamaño en y al conjunto . Afirmamos que  es una anticadena. Sea  una anticadena de tamaño que contenga . Fijemos índices distintos arbitrarios y . entonces _ deja _ Entonces por definición . De esto se deduce que , ya que . Si intercambiamos los roles y , obtenemos . Esto prueba que es una anticadena.

Volvamos a . Supongamos primero que para algunos . Sea  una cadena . Entonces, debido a la elección , no contiene una anticadena de tamaño . De la hipótesis de inducción se sigue que es posible cubrir con caminos disjuntos, ya que es una anticadena de tamaño en . Por lo tanto, es posible cubrir con cadenas que no se cruzan, según se requiera.

Ahora, si para cada , entonces es una anticadena de tamaño en (ya que  es el máximo en ). Así, puede estar cubierto por cadenas , lo que completa la demostración.

Demostración mediante el teorema de König

Al igual que otros resultados de la combinatoria, el teorema de Dilworth es equivalente al teorema de König sobre coincidencias en gráficos bipartitos y algunos otros teoremas, incluido el teorema de la boda de Hall [3] .

Para probar el teorema de Dilworth para un poset S con n elementos, usando el teorema de König, definimos un grafo bipartito G = ( U , V , E ) donde U = V = S y ( u , v ) es una arista en G si u < v a S. _ Por el teorema de König, existe un M coincidente en G y un conjunto de vértices C en G , de modo que cada arista del gráfico contiene al menos un vértice de C y ambos conjuntos, M y C , tienen el mismo número de elementos m . Sea A  el conjunto de elementos de S que no corresponden a ningún vértice de C. Entonces A tiene al menos n  - m elementos (posiblemente más si C contiene vértices correspondientes al mismo elemento en ambos lados del gráfico bipartito). Sea P la familia de  cadenas formada al incluir x e y en una cadena cuando hay una arista ( x , y ) en M. Entonces P tiene n  - m cadenas. Así, hemos construido una anticadena y una descomposición en cadenas con el mismo número de elementos en el conjunto.

Para demostrar el teorema de König a partir del teorema de Dilworth para un grafo bipartito G = ( U , V , E ) formamos un orden parcial en los vértices de G estableciendo u < v exactamente cuando u está contenido en U , v está contenido en V y no es una arista desde E desde u en v . Por el teorema de Dilworth, hay una anticadena A y una descomposición en cadena P , ambos conjuntos del mismo tamaño. Pero solo los pares de elementos correspondientes a los bordes del gráfico pueden ser cadenas no triviales en orden parcial, por lo que las cadenas no triviales de P forman una coincidencia en el gráfico. El complemento A forma una cubierta de vértice G con el mismo número de elementos que en el emparejamiento.

Esta conexión con coincidencias bipartitas permite calcular el ancho de cualquier conjunto ordenado en tiempo polinomial .

Generalización a conjuntos parcialmente ordenados ilimitados

El teorema de Dilworth para conjuntos parcialmente ordenados ilimitados establece que dicho conjunto tiene un ancho acotado w si y solo si puede descomponerse en w cadenas. Suponga que un poset infinito P tiene un ancho w , lo que significa que cualquier anticadena contiene como máximo un número finito w de elementos. Para cualquier subconjunto S de P , la descomposición en w cadenas (si existe) puede describirse como una coloración del gráfico de incomparabilidad S (un gráfico que tiene elementos de S como vértices y aristas para vértices incomparables) utilizando w colores. Cualquier clase de coloración de un gráfico de incomparabilidad debe ser una cadena. Asumiendo que P tiene ancho w , por la versión de caso finito del teorema de Dilworth, cualquier subconjunto finito S de P tiene una coloración w del gráfico de incomparabilidad. Así, por el teorema de de Bruijn-Erdős , P misma también tiene una coloración w del gráfico de incomparabilidad, y esta es la división deseada en cadenas [4] .

Sin embargo, el teorema no se generaliza tan fácilmente al caso de posets donde el ancho no está acotado. En este caso, el tamaño de la anticadena máxima y el número mínimo de hebras requeridas para la cobertura pueden diferir significativamente. En particular, para cualquier número cardinal infinito κ, existe un conjunto infinito parcialmente ordenado con ancho ℵ 0 cuya división en cadenas tiene al menos κ cadenas [4] .

En 1963 [5] , se obtuvo un enunciado similar al teorema de Dilworth para el caso ilimitado.

Teorema de Mirsky

El teorema dual al teorema de Dilworth, el teorema de Mirsky , afirma que el tamaño de la cadena más grande en un orden parcial (el caso final) es igual al menor número de anticadenas en las que se puede descomponer el orden parcial [6 ] . La demostración de este teorema es mucho más sencilla que la del teorema de Dilworth. Para cualquier elemento x , tome cadenas que tengan x como su elemento máximo, y sea N ( x ) el tamaño de la mayor de estas cadenas x -máximas . Entonces todo conjunto N −1 ( i ) formado por elementos que tienen los mismos valores de N es una anticadena, y el tamaño de esta división de un conjunto parcialmente ordenado en anticadenas es 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 vértices para cada elemento del orden y bordes para dos elementos comparables cualesquiera. Así, una clique en el gráfico de comparabilidad corresponde a una cadena y un conjunto independiente corresponde a una anticadena. Cualquier subgráfico generado de un gráfico de comparabilidad es en sí mismo un gráfico de comparabilidad formado a partir de un orden parcial al reducirse a un subconjunto de elementos.

Un grafo no dirigido es perfecto si el número cromático en cada subgrafo generado es igual al tamaño de la camarilla más grande. Cualquier gráfico de comparabilidad es perfecto: este es solo el teorema de Mirsky, explicado en términos de teoría de gráficos [7] . Por el teorema del gráfico perfecto de Lovas [8] , el complemento de cualquier gráfico perfecto también es un gráfico perfecto. Por lo tanto, el complemento de cualquier gráfico de comparabilidad es perfecto. Este es esencialmente el mismo teorema de Dilworth formulado en términos de teoría de grafos [7] . Por tanto, la propiedad de complementariedad de los gráficos perfectos puede proporcionar una prueba alternativa del teorema de Dilworth.

Ancho de pedidos parciales especiales

La red booleana B n  es el grado de un conjunto X de n elementos, por ejemplo, {1, 2, …, n }, ordenados por inclusión o, formalmente, (2 [ n ] , ⊆). El teorema de Sperner establece que la anticadena máxima en B n tiene un tamaño que no excede

En otras palabras, la familia más grande de subconjuntos de incomparabilidad de conjuntos X se obtiene eligiendo subconjuntos de X que tienen una media. La desigualdad de Lubell-Yamamoto-Meshalkin también está relacionada con anticadenas en potencias de un conjunto y puede usarse para demostrar el teorema de Sperner.

Si ordena los enteros en el intervalo [1, 2 n ] por divisibilidad , el subintervalo [ n + 1, 2 n ] forma una anticadena de tamaño n . La descomposición de este orden parcial en n cadenas es fácil de obtener: por cada m impar en [1,2 n ], formamos una cadena de números de la forma m 2 i . Así, por el teorema de Dilworth, el ancho de este orden parcial es n .

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

La "dimensión convexa" de un antimatroide se define como el número mínimo de cadenas necesarias para definir un antimatroide, y el teorema de Dilworth se puede usar para mostrar que es igual al ancho del orden parcial asociado. Esta relación conduce a un algoritmo lineal en el tiempo para encontrar una dimensión convexa [10] .

Notas

  1. ↑ Marshall Hall Jr. Teoría Combinatoria . - "MIR", 1970. - S. 90-94. Archivado el 14 de octubre de 2011 en Wayback Machine .
  2. ↑ Galvin, 1994 .
  3. ↑ Fulkerson, 1956 .
  4. ↑ 12 Harzheim , 2005 .
  5. ↑ Perlés, 1963 .
  6. ↑ Mirski, 1971 .
  7. ↑ 1 2 Bergé, Chvatal, 1984 .
  8. ↑ Lovasz, 1972 .
  9. ↑ Steele, 1995 .
  10. ↑ Edelman, Saks, 1988 .

Literatura