En matemáticas , en las áreas de teoría de órdenes 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 antichains . Lleva el nombre de Leon Mirsky ( 1971 ) y está estrechamente relacionado con el teorema de Dilworth sobre los anchos de órdenes parciales, con la perfección de los gráficos de comparabilidad , con el teorema de Gallai-Hasse-Roy-Vitaver que relaciona las trayectorias y coloraciones más largas en los gráficos, y con laTeorema de Erdős-Szekeres sobre subsecuencias monótonas.
El teorema
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 donde se sigue 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 antichains (subconjuntos en los que no hay ningún par de elementos ordenados) en los que se puede dividir el conjunto. En tal partición, cada dos elementos de la cadena más larga deben entrar en dos antichains diferentes, por lo que el número de antichains siempre es mayor o igual a la altura; otra formulación del teorema de Mirsky es que siempre existe una partición para la cual el número de antichains es igual a la altura. Nuevamente, en el ejemplo de enteros positivos ordenados por divisibilidad, los números se pueden dividir en antichains {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 probar la existencia de una partición en un pequeño número de antichains para un conjunto arbitrario finito parcialmente ordenado, considere para cada elemento x las cadenas que tienen x como su elemento más grande, y sea N ( x ) el tamaño del mayor de estos. 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. En su demostración original, Mirsky construye la misma partición inductivamente, eligiendo un antichain de los elementos máximos 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.
Resultados relacionados
Teorema de Dilworth
Mirsky se inspiró en el teorema de Dilworth , afirmando que, para cada conjunto parcialmente ordenado, el tamaño máximo de un antichain es igual al número mínimo de cadenas en una partición del conjunto en cadenas. Para conjuntos de orden dimensión dos, los dos teoremas coinciden (una cadena en el orden de mayorización de puntos en posición general en el plano es un antichain en el conjunto de puntos formado por una rotación de 90 ° desde el 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 probar.
El teorema de Mirsky y el teorema de Dilworth también están relacionados entre sí a través de la teoría de los gráficos perfectos . 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. En el gráfico de comparabilidad de un conjunto parcialmente ordenado, una camarilla representa una cadena y un color representa una partición en antichains, y los subgráficos inducidos de gráficos de comparabilidad son en sí mismos gráficos de comparabilidad, por lo que el teorema de Mirsky establece que los gráficos de comparabilidad son perfectos. De manera análoga, el teorema de Dilworth establece que todo gráfico de complemento de un gráfico de comparabilidad es perfecto. El teorema del gráfico perfecto de Lovász (1972) establece que los complementos de los gráficos perfectos son siempre perfectos y pueden utilizarse para deducir el teorema de Dilworth del teorema de Mirsky y viceversa ( Golumbic 1980 ).
Teorema de Gallai-Hasse-Roy-Vitaver
El teorema de Mirsky se puede reformular en términos de grafos acíclicos dirigidos (que representan un conjunto parcialmente ordenado por la accesibilidad de sus vértices), como el enunciado de que existe un homomorfismo de grafos desde un grafo acíclico dirigido dado G hasta un torneo transitivo de k- vértice si y solo si no existe un homomorfismo de a ( k -vertex + 1) gráfico de ruta a G . Porque, el gráfico de ruta más grande que tiene un homomorfismo a G da la cadena más larga en el orden de accesibilidad, y los conjuntos de vértices con la misma imagen en un homomorfismo a un torneo transitivo forman una partición en antichains. Esta declaración se generaliza al caso de que G no es acíclico, y es una forma del teorema de Gallai-Hasse-Roy-Vitaver sobre coloraciones y orientaciones de gráficos ( Nešetřil y Ossona de Mendez 2012 ).
Teorema de Erdős-Szekeres
Se deduce del teorema de Dilworth o del teorema de Mirsky que, en todo conjunto parcialmente ordenado de elementos rs + 1, debe existir una cadena de elementos r + 1 o un antichain de elementos s + 1. Mirsky (1971) utiliza esta observación, aplicada a un orden parcial de orden dimensión dos, para probar el teorema de Erdős-Szekeres de que en cada secuencia de rs + 1 elementos totalmente ordenados debe existir una subsecuencia creciente monótona de r + 1 elementos o una subsecuencia decreciente monótona de s + 1 elementos.
Extensiones
El teorema de Mirsky se extiende inmediatamente a infinitos conjuntos parcialmente ordenados con altura finita. Sin embargo, la relación entre la longitud de una cadena y el número de antichains en una partición en antichains no se extiende a cardinalidades infinitas: para cada número cardinal infinito κ, existen conjuntos parcialmente ordenados que no tienen una cadena infinita y que no tienen una partición antichain con κ o menos antichains ( Schmerl 2002 ).
Referencias
- 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.
- Golumbic, Martin Charles (1980), "5.7. Colorear y otros problemas sobre gráficos de comparabilidad", Teoría algorítmica de gráficos y gráficos perfectos , Nueva York: Academic Press, págs. 132-135, ISBN 0-12-289260-7, MR 0562306.
- 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", Dispersidad: Gráficos, Estructuras y Algoritmos (PDF) , Algoritmos y Combinatoria, 28 , Heidelberg: Springer, p. 42, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- Schmerl, James H. (2002), "Obstáculos para extender el teorema de Mirsky", Orden , 19 (2): 209-211, doi : 10.1023 / A: 1016541101728 , MR 1922918 , S2CID 26514679.