En matemáticas , en las áreas de teoría del orden y combinatoria , el teorema de Mirsky caracteriza la altura de cualquier conjunto finito parcialmente ordenado en términos de una partición del orden en un número mínimo de anticadenas . Recibe su nombre en honor a Leon Mirsky (1971) y está estrechamente relacionado con el teorema de Dilworth sobre los anchos de los órdenes parciales, con el teorema de perfección de los grafos de comparabilidad , con el teorema de Gallai-Hasse-Roy-Vitaver que relaciona los caminos más largos y las coloraciones en los grafos, y con el teorema de Erdős-Szekeres sobre subsecuencias monótonas.
La altura de un conjunto parcialmente ordenado se define como la cardinalidad máxima de una cadena , un subconjunto totalmente ordenado del orden parcial dado. Por ejemplo, en el conjunto de números enteros positivos de 1 a N , ordenados por divisibilidad , una de las cadenas más grandes consiste en las potencias de dos que se encuentran dentro de ese rango, de lo que se deduce que la altura de este orden parcial es .
El teorema de Mirsky establece que, para cada conjunto finito parcialmente ordenado, la altura también es igual al número mínimo de anticadenas (subconjuntos en los que no se ordenan pares de elementos) en los que se puede dividir el conjunto. En una partición de este tipo, cada dos elementos de la cadena más larga deben ir en dos anticadenas diferentes, por lo que el número de anticadenas siempre es mayor o igual que la altura; otra formulación del teorema de Mirsky es que siempre existe una partición para la que el número de anticadenas es igual a la altura. De nuevo, en el ejemplo de los números enteros positivos ordenados por divisibilidad, los números se pueden dividir en las anticadenas {1}, {2,3}, {4,5,6,7}, etc. Hay conjuntos en esta partición, y dentro de cada uno de estos conjuntos, cada par de números forma una razón menor que dos, por lo que no hay dos números dentro de uno de estos conjuntos que puedan ser divisibles.
Para demostrar la existencia de una partición en un pequeño número de anticadenas para un conjunto arbitrario finito parcialmente ordenado, considérese para cada elemento x las cadenas que tienen x como su elemento más grande, y sea N ( x ) el tamaño de la más grande de estas cadenas x -maximales. Entonces cada conjunto N −1 ( i ), que consiste en 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. En su demostración original, Mirsky construye la misma partición inductivamente, eligiendo una anticadena de los elementos maximos de las cadenas más largas, y mostrando que la longitud de la cadena más larga entre los elementos restantes se reduce en uno.
Mirsky se inspiró en el teorema de Dilworth , que afirma que, para cada conjunto parcialmente ordenado, el tamaño máximo de una anticadena es igual al número mínimo de cadenas en una partición del conjunto en cadenas. Para conjuntos de dimensión de orden dos, los dos teoremas coinciden (una cadena en el orden de mayoración de puntos en posición general en el plano es una anticadena en el conjunto de puntos formado por una rotación de 90° respecto del conjunto original, y viceversa), pero para órdenes parciales más generales los dos teoremas difieren y (como observa Mirsky) el teorema de Dilworth es más difícil de demostrar.
El teorema de Mirsky y el teorema de Dilworth también están relacionados entre sí a través de la teoría de grafos perfectos . Un grafo 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. En el grafo de comparabilidad de un conjunto parcialmente ordenado, una camarilla representa una cadena y una coloración representa una partición en anticadenas, y los subgrafos inducidos de los grafos de comparabilidad son en sí mismos grafos de comparabilidad, por lo que el teorema de Mirsky establece que los grafos de comparabilidad son perfectos. Análogamente, el teorema de Dilworth establece que todo grafo complementario de un grafo de comparabilidad es perfecto. El teorema del grafo perfecto de Lovász (1972) establece que los complementos de los grafos perfectos son siempre perfectos, y puede usarse para deducir el teorema de Dilworth a partir del teorema de Mirsky y viceversa (Golumbic 1980).
El teorema de Mirsky puede reformularse en términos de grafos acíclicos dirigidos (que representan un conjunto parcialmente ordenado por la alcanzabilidad de sus vértices), como la afirmación de que existe un homomorfismo de grafos desde un grafo acíclico dirigido dado G hasta un torneo transitivo de k -vértices si y solo si no existe un homomorfismo desde un grafo de trayectorias de ( k + 1)-vértices hasta G . Porque, el grafo de trayectorias más grande que tiene un homomorfismo hacia G da la cadena más larga en el orden de alcanzabilidad, y los conjuntos de vértices con la misma imagen en un homomorfismo hacia un torneo transitivo forman una partición en anticadenas. Esta afirmación se generaliza al caso de que G no sea acíclico, y es una forma del teorema de Gallai–Hasse–Roy–Vitaver sobre coloraciones y orientaciones de grafos (Nešetřil & Ossona de Mendez 2012).
Del teorema de Dilworth o del teorema de Mirsky se deduce que, en cada conjunto parcialmente ordenado de rs + 1 elementos, debe existir una cadena de r + 1 elementos o una anticadena de s + 1 elementos. Mirsky (1971) utiliza esta observación, aplicada a un orden parcial de dimensión de orden dos, para demostrar el teorema de Erdős-Szekeres que establece que en cada secuencia de rs + 1 elementos totalmente ordenados debe existir una subsecuencia monótonamente creciente de r + 1 elementos o una subsecuencia monótonamente decreciente de s + 1 elementos.
El teorema de Mirsky se extiende inmediatamente a conjuntos parcialmente ordenados infinitos con altura finita. Sin embargo, la relación entre la longitud de una cadena y el número de anticadenas en una partición en anticadenas no se extiende a cardinalidades infinitas: para cada número cardinal infinito κ, existen conjuntos parcialmente ordenados que no tienen cadena infinita y que no tienen una partición de anticadena con κ o menos anticadenas (Schmerl 2002).
