En la teoría del orden , una rama de las matemáticas, la conjetura 1 / 3-2 / 3 establece que, si uno está ordenando por comparación un conjunto de elementos, entonces, independientemente de las comparaciones que ya se hayan realizado, siempre es posible elegir la siguiente. comparación de tal manera que reducirá el número de posibles pedidos clasificados en un factor de 2/3 o mejor. De manera equivalente, en cada finito conjunto parcialmente ordenado que no está totalmente ordenó , existe un par de elementos de x y y con la propiedad de que al menos un tercio y como máximo 2/3 de las extensiones lineales del lugar de orden parcial x antes de lo y .
Ejemplo
El orden parcial formado por tres elementos una , b , y c con una sola relación comparabilidad, un ≤ b , tiene tres extensiones lineales, un ≤ b ≤ c , un ≤ c ≤ b , y c ≤ un ≤ b . En estas tres extensiones, a es anterior a b . Sin embargo, a es anterior a c en solo dos de ellos y posterior a c en el tercero. Por lo tanto, el par de un y c tienen la propiedad deseada, mostrando que este orden parcial obedece la conjetura de 1 / 3-2 / 3.
Este ejemplo muestra que las constantes 1/3 y 2/3 en la conjetura son ajustadas; si q es cualquier fracción estrictamente entre 1/3 y 2/3, entonces no existiría un par x , y en el que x sea anterior a y en un número de ordenamientos parciales que esté entre q y 1 - q multiplicado por el número total de pedidos parciales. [1]
De manera más general, sea P cualquier composición en serie de órdenes parciales de tres elementos y de órdenes parciales de un elemento, como la de la figura. Entonces P forma un caso extremo para la conjetura 1 / 3-2 / 3 en el sentido de que, para cada par x , y de elementos, uno de los dos elementos ocurre antes que el otro en como máximo 1/3 de las extensiones lineales de P . Los pedidos parciales con esta estructura son necesariamente semiordenes en serie-paralelos ; son los únicos casos extremos conocidos para la conjetura y se puede probar que son los únicos casos extremos con ancho dos. [2]
Definiciones
Un conjunto parcialmente ordenado es un conjunto X junto con una relación binaria ≤ que es reflexiva , antisimétrica y transitiva . Un orden total es un orden parcial en el que cada par de elementos es comparable. Una extensión lineal de un orden parcial finito es un orden secuencial de los elementos de X , con la propiedad de que si x ≤ y en el orden parcial, entonces x debe estar antes que y en la extensión lineal. En otras palabras, es un orden total compatible con el orden parcial. Si un conjunto finito parcialmente ordenado está totalmente ordenado, entonces solo tiene una extensión lineal, pero de lo contrario tendrá más de una. Los 1 / 3-2 / 3 conjetura estados que uno puede elegir dos elementos x y y de tal manera que, entre este conjunto de posibles extensiones lineales, entre 1/3 y 2/3 de ellos lugar x antes de y , y simétricamente entre 1 / 3 y 2/3 de ellos colocan y antes que x . [3]
Existe un enunciado alternativo y equivalente de la conjetura 1 / 3–2 / 3 en el lenguaje de la teoría de la probabilidad . Se puede definir una distribución de probabilidad uniforme en las extensiones lineales en la que es igualmente probable que se elija cada extensión lineal posible. Los estados 1 / 3-2 / 3 conjetura de que, en virtud de esta distribución de probabilidad, existe un par de elementos de x y y de tal manera que la probabilidad de que x es anterior a y en una extensión lineal aleatorio es entre 1/3 y 2/3 . [3]
Kahn y Saks (1984) definen δ ( P ), para cualquier conjunto parcialmente ordenado P , como el mayor número real δ tal que P tiene un par x , y con x antes que y en un número de extensiones lineales que está entre δ y 1 - δ del número total de extensiones lineales. En esta notación, la conjetura 1 / 3–2 / 3 establece que cada orden parcial finito que no es total tiene δ ( P ) ≥ 1/3 .
Historia
La conjetura 1 / 3–2 / 3 fue formulada por Kislitsyn (1968) , y luego realizada de forma independiente por Michael Fredman [4] y Nati Linial ( 1984 ). [3] Fue catalogado como un problema destacado sin resolver en la fundación de la revista Order , y sigue sin resolverse; [3] Brightwell, Felsner y Trotter (1995) lo llaman "uno de los problemas más intrigantes en la teoría combinatoria de posets".
Brightwell (1999) ofrece un resumen de la conjetura .
Resultados parciales
Se sabe que la conjetura 1 / 3–2 / 3 es cierta para ciertas clases especiales de órdenes parciales, incluyendo órdenes parciales de ancho dos, [5] órdenes parciales de altura dos, [6] órdenes parciales con un máximo de 11 elementos, [ 7] órdenes parciales en los que cada elemento es incomparable con otros seis como máximo, [8] órdenes parciales serie-paralelos , [9] y semiorderes . [10] En el límite cuando n va al infinito, la proporción de órdenes parciales de n elementos que obedecen a la conjetura 1 / 3–2 / 3 se aproxima al 100%. [7]
Brightwell, Felsner y Trotter (1995) demostraron que, para cualquier orden parcial finita P que no es total, δ ( P ) ≥ 1/2 - √ 5 /10 ≈ 0.276. Sus resultados mejoran los límites anteriores más débiles del mismo tipo. [11] Usan la interpretación probabilística de δ ( P ) para extender su definición a ciertos órdenes parciales infinitos; en ese contexto, muestran que sus límites son óptimas, en que existen órdenes parciales infinitos con δ ( P ) = 1/2 - √ 5 /10.
Aplicaciones
Kahn y Saks (1984) propusieron la siguiente aplicación para el problema: los deseos de uno supone que la comparación tipo un conjunto totalmente ordenado X , para el que alguna información de orden parcial ya se conoce en la forma de un orden parcial en X . En el peor de los casos, cada comparación adicional entre un par x y y de elementos puede dar como poca información como sea posible, mediante la resolución de la comparación de una manera que las hojas como muchas extensiones lineales como sea posible compatible con el resultado de la comparación. La conjetura 1 / 3–2 / 3 establece que, en cada paso, se puede elegir una comparación para realizar que reduzca el número restante de extensiones lineales en un factor de 2/3; por lo tanto, si hay extensiones E lineales del orden parcial dado por la información inicial, el problema de clasificación se puede completar en como máximo log 3/2 E comparaciones adicionales.
Sin embargo, este análisis descuida la complejidad de la selección de la óptima par x y y para comparar. Además, puede ser posible ordenar un orden parcial usando una serie de comparaciones que sea mejor de lo que sugiere este análisis, porque puede que no sea posible que este comportamiento en el peor de los casos ocurra en cada paso de un algoritmo de ordenación. En esta dirección, se ha conjeturado que las comparaciones log φ E pueden ser suficientes, donde φ denota la proporción áurea . [7]
Una clase estrechamente relacionada de problemas de clasificación de comparación es considerado por Fredman (1976) , entre ellos el problema de la comparación de clasificación de un conjunto X cuando el orden de clasificación de X se sabe que se encuentran en algún conjunto S de permutaciones de X . Aquí S no se genera necesariamente como el conjunto de extensiones lineales de un orden parcial. A pesar de esta generalidad adicional, Fredman muestra que X se puede ordenar usando log 2 | S | + O (| X |) comparaciones. Este mismo límite se aplica también al caso de órdenes parciales y muestra que las comparaciones log 2 E + O ( n ) son suficientes.
Kahn y Saks (1984) conjeturaron que, en el límite cuando w tiende a infinito, el valor de δ ( P ) para conjuntos parcialmente ordenados de ancho w debería tender a 1/2. En particular, esperan que solo los conjuntos parcialmente ordenados de ancho dos puedan alcanzar el peor valor de caso δ ( P ) = 1/3, y Aigner (1985) estableció esto explícitamente como una conjetura. El valor más pequeño conocido de δ ( P ) para posets de ancho tres es 14/39, [12] y las búsquedas informáticas han demostrado que no es posible un valor menor para posets de ancho 3 con nueve o menos elementos. [6]
Marcin Peczarski [7] [8] ha formulado una "conjetura de partición de oro" afirmando que en cada orden parcial que no es un orden total se pueden encontrar dos comparaciones consecutivas de modo que, si t i denota el número de extensiones lineales que quedan después de i de se han realizado las comparaciones, entonces (en cada uno de los cuatro posibles resultados de las comparaciones) t 0 ≥ t 1 + t 2 . Si esta conjetura es cierta, implicaría la conjetura de 1 / 3–2 / 3: la primera de las dos comparaciones debe ser entre un par que divide las comparaciones restantes por, en el peor de los casos, una razón de 1 / 3–2 / 3. La conjetura de la partición de oro también implicaría que un orden parcial con extensiones lineales E puede clasificarse en la mayoría de las comparaciones log φ E ; el nombre de la conjetura se deriva de esta conexión con la proporción áurea.
Es # P-completa , dado un orden parcial finita P y un par de elementos de x y y , para calcular la proporción de las extensiones lineales de P ese lugar x antes de y . [13]
Notas
- ^ Kahn y Saks (1984) ; Brightwell, Felsner y Trotter (1995) .
- ^ Aigner (1985) .
- ↑ a b c d Brightwell, Felsner y Trotter (1995) .
- ↑ Sin embargo, a pesar de la estrecha conexión de Fredman (1976) con el problema de clasificar datos parcialmente ordenados y, por lo tanto, con la conjetura 1 / 3-2 / 3, no se menciona en ese artículo.
- ^ Linial (1984) , Teorema 2.
- ↑ a b Trotter, Gehrlein y Fishburn (1992) .
- ↑ a b c d Peczarski (2006) .
- ↑ a b Peczarski (2008) .
- ↑ Zaguia (2012)
- ^ Brightwell (1989) .
- ^ Kahn y Saks (1984) ; Khachiyan (1989) ; Kahn y Linial (1991) ; Felsner y Trotter (1993) .
- ^ Saks (1985) .
- ^ Brightwell y Winkler (1991) .
Referencias
- Aigner, Martin (1985), "A note on merging" , Order , 2 (3): 257-264, doi : 10.1007 / BF00333131 (inactivo el 31 de mayo de 2021)Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace ).
- Brightwell, Graham R. (1989), "Semiorders and the 1 / 3-2 / 3 conjecture", Order , 5 (4): 369-380, doi : 10.1007 / BF00353656 , S2CID 86860160.
- Brightwell, Graham R. (1999), "Pares equilibrados en órdenes parciales", Matemáticas discretas , 201 (1-3): 25-52, doi : 10.1016 / S0012-365X (98) 00311-2.
- Brightwell, Graham R .; Felsner, Stefan; Trotter, William T. (1995), "Pares de equilibrio y la conjetura del producto cruzado", Order , 12 (4): 327–349, CiteSeerX 10.1.1.38.7841 , doi : 10.1007 / BF01110378 , MR 1368815 , S2CID 14793475.
- Brightwell, Graham R .; Winkler, Peter (1991), "Contando extensiones lineales", Pedido , 8 (3): 225–242, doi : 10.1007 / BF00383444 , S2CID 119697949.
- Felsner, Stefan; Trotter, William T. (1993), "Equilibrio de pares en conjuntos parcialmente ordenados", Combinatoria, Paul Erdős tiene ochenta , Bolyai Society Mathematical Studies, 1 , Budapest: János Bolyai Mathematical Society , pp. 145-157, MR 1249709.
- Fredman, ML (1976), "¿Qué tan buena es la teoría de la información ligada a la clasificación?", Informática teórica , 1 (4): 355–361, doi : 10.1016 / 0304-3975 (76) 90078-5
- Kahn, Jeff; Linial, Nati (1991), "Balancing extensions via Brunn-Minkowski", Combinatorica , 11 (4): 363–368, doi : 10.1007 / BF01275670 , S2CID 206793172.
- Kahn, Jeff; Saks, Michael (1984), "Equilibrio de extensiones de poset", Pedido , 1 (2): 113–126, doi : 10.1007 / BF00565647 , S2CID 123370506.
- Khachiyan, Leonid (1989), "Algoritmos óptimos en la descomposición y clasificación de programación convexa", en Jaravlev, J. (ed.), Computers and Decision Problems (en ruso), Moscú: Nauka, págs. 161-205. Según lo citado por Brightwell, Felsner y Trotter (1995) .
- Kislitsyn, SS (1968), "Un conjunto finito parcialmente ordenado y su correspondiente conjunto de permutaciones", Mathematical Notes , 4 (5): 798–801, doi : 10.1007 / BF01111312 , S2CID 120228193.
- Linial, Nati (1984), "El límite de la teoría de la información es bueno para fusionar", SIAM Journal on Computing , 13 (4): 795–801, doi : 10.1137 / 0213049 , S2CID 5149351.
- Peczarski, Marcin (2006), "La conjetura de la partición de oro", Orden , 23 (1): 89–95, doi : 10.1007 / s11083-006-9033-1 , S2CID 42415160.
- Peczarski, Marcin (2008), "La conjetura de la partición de oro para posets delgados 6", Orden , 25 (2): 91–103, doi : 10.1007 / s11083-008-9081-9 , S2CID 42034095.
- Saks, Michael (1985), "Equilibrio de extensiones lineales de conjuntos ordenados" , Problemas no resueltos, Orden , 2 : 327–330, doi : 10.1007 / BF00333138 (inactivo 31 de mayo de 2021)Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace )
- Trotter, William T .; Gehrlein, William V .; Fishburn, Peter C. (1992), "Teoremas de equilibrio para posiciones de altura-2", Orden , 9 (1): 43–53, doi : 10.1007 / BF00419038 , S2CID 16157076.
- Zaguia, Imed (2012), "La conjetura 1 / 3-2 / 3 para conjuntos ordenados libres de N ", Electronic Journal of Combinatorics , 19 (2): P29, arXiv : 1107.5626 , Bibcode : 2011arXiv1107.5626Z , doi : 10.37236 / 2345 , S2CID 1979845.