Teorema de Dilworth

Sea S un conjunto finito parcialmente ordenado . El tamaño de una antistring máxima es igual al tamaño de una cobertura de string mínima de S . Esto se llama el teorema de Dilworth . Lleva el nombre del matemático Robert P. Dilworth (1950).

El ancho de un conjunto finito parcialmente ordenado S es el tamaño máximo de una antistring en S. En otras palabras, el ancho de un conjunto finito parcialmente ordenado S es el número mínimo de strings necesarias para cubrir S, es decir, el número mínimo de strings tales que cualquier elemento de S está en al menos una de las strings.

Definición de string : Una string en un conjunto parcialmente ordenado es un subconjunto de elementos que son todos comparables entre sí.
Definición de antistring : una antistring es un subconjunto de elementos, ninguno de los cuales es comparable entre sí.

Ejemplos ilustrativos:

Let S be the set of divisors of 30, with divisibility as the partial order. 
Then the following chains cover S : 
{1, 2, 6, 30}, {3, 15}, {5, 10}

And {2, 3, 5} is an antichain of length 3. 
It is not immediately obvious, but the chain cover is minimal (though not unique), 
and the antichain is maximal (though not unique). 

So both definitions of width give 3 for this partially ordered set. 

Prueba del Teorema de Dilworth:
La prueba más sencilla es por inducción sobre el tamaño del conjunto. Sea d el tamaño de la antistring más grande de S. La prueba mostrará que S puede estar cubierto por d strings. El caso base es trivial. Supongamos que el resultado ha sido probado para todos los conjuntos menores que S.

Primero, si no hay dos elementos de S que sean comparables, entonces S en sí mismo es una antistring y puede ser cubierto por d = |S| strings cada una de longitud 1, por lo que el resultado se mantiene. De lo contrario, sea m un elemento mínimo (m <= z para todos los z comparables) y M un elemento máximo (z <= M para todos los z comparables). Sea T = S – {m, M}. Si la antistring más grande en T tiene un tamaño <= d – 1, entonces T puede estar cubierta por d – 1 strings, y así S puede estar cubierta por aquellas más la string {m, M}, y el resultado se probará para S .

Ahora, suponga que la antistring más grande en T tiene un tamaño d (no puede ser más grande porque T es un subconjunto de S). Llame a esta antistring A.

La idea del resto de la prueba es: imagina el diagrama de Hasse para S donde la antistring más grande consiste en una tira horizontal. Tome todo lo que está debajo de la tira y todo lo que está encima de la tira, use la inducción para cubrirlos con strings y luego una las strings conectándolas a través de la tira.

Es decir, construya los dos conjuntos

S ⁺ = {x pertenece a S:x >= a para algún a pertenece a A}
S ^– = {x pertenece a S:x <= a para algún a pertenece a A}

Entonces S ⁺ US ^– debe ser todo S, porque si no lo fuera entonces A no sería una antistring maximal en S. Y S ⁺ US ^– = A, porque si x está en la intersección, entonces a <= x < = b para algunos elementos a, b pertenece a A, entonces a y b son comparables por transitividad, entonces la única posibilidad es que a = b y ambos sean iguales a x.

Dado que m y M no están en A, debe darse el caso de que y m no pertenezca a S+, y m no pertenezca a S-, por lo que ambos conjuntos son estrictamente más pequeños que S. La hipótesis inductiva se aplica a ambos S ^– y S ⁺ , por lo que ambos están cubiertos por d strings, cada una de las cuales debe contener exactamente un elemento de A. Llámelas C _a ^– y C _a ⁺ . Ahora podemos unir estas cubiertas para obtener una cubierta de todo S, mediante las strings C _a ^– U {a} UC _a ⁺ . Esta cubierta tiene strings d, por lo que el resultado se sigue por inducción.

Código para ilustrar el ejemplo anterior:
El algoritmo clásico O(N lg N) para la subsecuencia creciente más larga (LIS) puede verse como una aplicación del teorema de Dilworth. Ver aquí _

Referencias: Video de Youtube