Una anticadena en un conjunto parcialmente ordenado es un conjunto de elementos sin dos comparables entre sí, y una cadena es un conjunto de elementos comparables dos a dos. 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 mayor tiene el mismo tamaño que la descomposición en cadena menor. En este caso, 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 la de Galvin (1994).

Sea ${\displaystyle P}$  un conjunto finito parcialmente ordenado. El teorema se cumple trivialmente si ${\displaystyle P}$  está vacío. Por lo tanto, supóngase que ${\displaystyle P}$  tiene al menos un elemento, y sea ${\displaystyle a}$  un elemento maximal de ${\displaystyle P}$ .

Por inducción, se asume que, para algún entero ${\displaystyle k}$ , el conjunto parcialmente ordenado ${\displaystyle P':=P\setminus \{a\}}$  puede estar cubierto por ${\displaystyle k}$  cadenas disjuntas de ${\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}$ , sea ${\displaystyle x_{i}}$  el elemento máximo de ${\displaystyle C_{i}}$  que pertenece a una anticadena de tamaño ${\displaystyle k}$  en ${\displaystyle P'}$ , y el conjunto ${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$ .

Ahora se afirma que ${\displaystyle A}$  es una anticadena.

Sea ${\displaystyle A_{i}}$  una anticadena de tamaño ${\displaystyle k}$  que contiene a ${\displaystyle x_{i}}$ . Se fijan índices arbitrarios distintos ${\displaystyle i}$  y ${\displaystyle j}$ . Luego, ${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$ . Sea ${\displaystyle y\in A_{i}\cap C_{j}}$ . Luego, ${\displaystyle y\leq x_{j}}$ , por la definición de ${\displaystyle x_{j}}$ . Esto implica que ${\displaystyle x_{i}\not \geq x_{j}}$ , ya que ${\displaystyle x_{i}\not \geq y}$ . Al intercambiar los roles de ${\displaystyle i}$  y ${\displaystyle j}$  en este argumento, también se tiene que ${\displaystyle x_{j}\not \geq x_{i}}$ . Esto verifica que ${\displaystyle A}$  es una anticadena.

Ahora se vuelve sobre ${\displaystyle P}$ . Supóngase primero que ${\displaystyle a\geq x_{i}}$  para algún ${\displaystyle i\in \{1,2,\dots ,k\}}$ . Sea ${\displaystyle K}$  la cadena ${\displaystyle \{a\}\cup \{z\in C_{i}:z\leq x_{i}\}}$ . Entonces, al elegir ${\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 ser cubierto por ${\displaystyle k-1}$  cadenas disjuntas, ya que ${\displaystyle A\setminus \{x_{i}\}}$  es una anticadena de tamaño ${\displaystyle k-1}$  en ${\displaystyle P\setminus K}$ .

Por lo tanto, ${\displaystyle P}$  puede ser cubierto por ${\displaystyle k}$  cadenas disjuntas, como se requiere. 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}$  (ya que ${\displaystyle a}$  es maximal en ${\displaystyle P}$ ). Ahora ${\displaystyle P}$  puede ser cubierto por las cadenas ${\displaystyle k+1}$  ${\displaystyle \{a\},C_{1},C_{2},\dots ,C_{k}}$ , completando la demostración.

Al igual que otros resultados en combinatoria, el teorema de Dilworth es equivalente al teorema de Kőnig en el emparejamiento de un grafo bipartito y a varios otros teoremas relacionados, incluyendo el teorema de Hall.^[2]​

Para demostrar el teorema de Dilworth para un orden parcial S con n elementos, utilizando el teorema de König, defínase 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. Según el teorema de König, existe una M coincidente en G y un conjunto de vértices C en G, de modo que cada arista del grafo contiene al menos un vértice en C y 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í. 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, se ha 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), se forma un orden parcial en los vértices de G donde u < v exactamente cuando u está en U, v está en V y 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, ambas del mismo tamaño. Sin embargo, las únicas cadenas no triviales en el orden parcial son pares de elementos correspondientes 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 la anchura de cualquier orden parcial en tiempo polinómico. Más precisamente, órdenes parciales de n elementos de anchura k puede reconocerse en tiempo O(kn²). ^[3]​

El teorema de Dilworth para conjuntos infinitos parcialmente ordenados establece que un conjunto parcialmente ordenado tiene una anchura finita w si y solo si puede dividirse en w cadenas. Supóngase que un orden parcial infinito P tiene anchura 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 un 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) utilizando w colores; cada clase de color en una coloración adecuada del grafo de incomparabilidad debe ser una cadena. Suponiendo que P tiene una anchura w, y según la versión finita del teorema de Dilworth, todo subconjunto finito S de P tiene un grafo de incomparabilidad coloreable w. Por lo tanto, según el teorema de De Bruijn–Erdős, P también tiene un grafo de incomparabilidad w coloreable y, por lo tanto, la partición deseada en cadenas.^[4]​

Sin embargo, el teorema no se aplica de forma tan simple a conjuntos parcialmente ordenados en los que la anchura, y no solo 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 orden parcial pueden ser muy diferentes. En particular, para cada número cardinal infinito κ existe un conjunto parcialmente ordenado infinito de anchura ℵ₀ cuya partición en el menor número de cadenas tiene κ cadenas.^[4]​

Perles (1963) analiza analogías 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 menor número de anticadenas en las que se puede dividir el orden.^[5]​ Este postulado se conoce como el teorema de Mirsky. Su demostración es mucho más sencilla que la del propio teorema de Dilworth: para cualquier elemento «x», considérense las cadenas que tienen x como su elemento más grande, y sea N(x) el tamaño de la mayor de estas cadenas x-máximas. Entonces, cada conjunto N⁻¹(i), compuesto por 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 grafo de comparabilidad es un grafo 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. Por lo tanto, un clique en un grafo de comparabilidad corresponde a una cadena, y un conjunto independiente en un grafo de comparabilidad corresponde a una anticadena. Cualquier subgrafo inducido de un grafo de comparabilidad es en sí mismo 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úmrto cromático es igual al tamaño del clique más grande. Todo grafo de comparabilidad es perfecto: esto es esencialmente el teorema de Mirsky, reformulado en términos de teoría de grafos. ^[6]​ Por 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 en sí mismo, reformulado en términos de la teoría de grafos por (Berge y Chvátal, 1984). Por lo tanto, 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 de n elementos X -esencialmente 1, 2, ..., n- ordenado por inclusión o, en notación algebraica, (2^[n], ⊆). El teorema de Sperner establece que una anticadena máxima de B_n tiene un tamaño máximo de

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

En otras palabras, la mayor familia 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 las anticadenas en un conjunto potencia y puede utilizarse para demostrar el teorema de Sperner.

Si se ordenan los enteros en el intervalo [1, 2n] por su divisibilidad, el subintervalo [n+1, 2n] 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, 2n], se forma una cadena de números de la forma m2ⁱ. Por lo tanto, según el teorema de Dilworth, la anchura de este orden parcial es n.

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

La dimensión convexa de un antimatroide se define como el número mínimo de cadenas necesario para definir el antimatroide, y el teorema de Dilworth puede utilizarse para demostrar que es igual a la anchura de un orden parcial asociado. Esta conexión conduce a un algoritmo de tiempo polinomial para dimensión convexa.^[8]​

• Berge, Claude; Chvátal, Václav (1984), Topics on Perfect Graphs, Annals of Discrete Mathematics 21, Elsevier, p. viii, ISBN 978-0-444-86587-8 .
• Dilworth, Robert P. (1950), «A Decomposition Theorem for Partially Ordered Sets», Annals of Mathematics 51 (1): 161-166, JSTOR 1969503, doi:10.2307/1969503 ..
• Edelman, Paul H.; Saks, Michael E. (1988), «Combinatorial representation and convex dimension of convex geometries», Order 5 (1): 23-32, S2CID 119826035, doi:10.1007/BF00143895 ..
• Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), «Recognition algorithms for orders of small width and graphs of small Dilworth number», Order 20 (4): 351-364 (2004), MR 2079151, S2CID 1363140, doi:10.1023/B:ORDE.0000034609.99940.fb ..
• Fulkerson, D. R. (1956), «Note on Dilworth's decomposition theorem for partially ordered sets», Proceedings of the American Mathematical Society 7 (4): 701-702, JSTOR 2033375, doi:10.2307/2033375 ..
• Galvin, Fred (1994), «A proof of Dilworth's chain decomposition theorem», The American Mathematical Monthly 101 (4): 352-353, JSTOR 2975628, MR 1270960, doi:10.2307/2975628 ..
• Greene, Curtis; Kleitman, Daniel J. (1976), «The structure of Sperner ${\displaystyle k}$ -families», Journal of Combinatorial Theory, Series A 20 (1): 41-68, doi:10.1016/0097-3165(76)90077-7 ..
• Harzheim, Egbert (2005), Ordered sets, Advances in Mathematics (Springer) 7, New York: Springer, Theorem 5.6, p. 60, ISBN 0-387-24219-8, MR 2127991 ..
• Lovász, László (1972), «Normal hypergraphs and the perfect graph conjecture», Discrete Mathematics 2 (3): 253-267, doi:10.1016/0012-365X(72)90006-4 ..
• Mirsky, Leon (1971), «A dual of Dilworth's decomposition theorem», American Mathematical Monthly 78 (8): 876-877, JSTOR 2316481, doi:10.2307/2316481 ..
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), «Theorem 3.13», Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 ..
• Perles, Micha A. (1963), «On Dilworth's theorem in the infinite case», Israel Journal of Mathematics 1 (2): 108-109, MR 0168497, S2CID 120943065, doi:10.1007/BF02759806 ..
• Steele, J. Michael (1995), «Variations on the monotone subsequence theme of Erdős and Szekeres», en Aldous, David; Diaconis, Persi; Spencer, Joel et al., eds., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications 72, Springer-Verlag, pp. 111-131 .

• Robert D. Borgersen (26 de noviembre de 2004), Equivalence of seven major theorems in combinatorics, archivado desde el original el 21 de julio de 2011 .
• «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, archivado desde el original el 20 de julio de 2011 .
• Felsner, S.; Raghavan, V.; Spinrad, J. (1999), Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number .
• Weisstein, Eric W. «Dilworth's Lemma». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.