Hispanopedia Wiki
Articulo de referencia

Lema del apretón de manos

En este grafo, un número par de vértices (los cuatro vértices numerados 2, 4, 5 y 6) tienen grados impares. La suma de los grados de los seis vértices es 2 + 3 + 2 + 3 + 3 + 1 =...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

En este grafo, un número par de vértices (los cuatro vértices numerados 2, 4, 5 y 6) tienen grados impares. La suma de los grados de los seis vértices es 2 + 3 + 2 + 3 + 3 + 1 = 14 , el doble del número de aristas.

En teoría de grafos , el lema del apretón de manos afirma que, en todo grafo finito no dirigido , el número de vértices que tocan un número impar de aristas es par. Por ejemplo, si hay un grupo de personas que se dan la mano, el número de personas que estrechan la mano de un número impar de otras personas es par. [ 1 ] El lema del apretón de manos es una consecuencia de la fórmula de la suma de grados , también llamada a veces lema del apretón de manos, [ 2 ] según la cual la suma de los grados (el número de veces que se toca cada vértice) es igual al doble del número de aristas en el grafo. Ambos resultados fueron demostrados por Leonhard Euler ( 1736 ) en su famoso artículo sobre los Siete Puentes de Königsberg , que dio inicio al estudio de la teoría de grafos. [ 3 ] 

Más allá del problema de los siete puentes de Königsberg, que formalizó posteriormente los recorridos eulerianos , otras aplicaciones de la fórmula de la suma de grados incluyen demostraciones de ciertas estructuras combinatorias. Por ejemplo, en las demostraciones del lema de Sperner y del problema de la escalada de montañas, las propiedades geométricas de la fórmula suelen aparecer. La clase de complejidad PPA encapsula la dificultad de encontrar un segundo vértice impar, dado un vértice de este tipo en un grafo grande definido implícitamente .

Definiciones y declaración

Un grafo no dirigido consta de un sistema de vértices y aristas que conectan pares no ordenados de vértices. En cualquier grafo, el gradogrados⁡(v){\displaystyle \deg(v)}de un vérticev{\displaystyle v}se define como el número de aristas que tienenv{\displaystyle v}como punto final. Para los grafos que pueden contener bucles que conectan un vértice consigo mismo, un bucle debe contarse como contribuyente de dos unidades al grado de su punto final para los fines del lema de la prueba de la mano. [ 2 ] Entonces, el lema de la prueba de la mano establece que, en todo grafo finito, debe haber un número par de vértices para los cualesgrados⁡(v){\displaystyle \deg(v)}es un número impar. [ 1 ] Los vértices de grado impar en un grafo a veces se denominan nodos impares (o vértices impares ); [ 4 ] en esta terminología, el lema del apretón de manos puede reformularse como la afirmación de que todo grafo tiene un número par de nodos impares. [ 4 ] [ 5 ]

La fórmula de suma de grados establece que ∑v∈Vgrados⁡v=2|mi|,{\displaystyle \sum _ {v\in V}\deg v=2|E|,} dóndeV{\displaystyle V}es el conjunto de nodos (o vértices) en el grafo ymi{\displaystyle E}es el conjunto de aristas en el grafo. Es decir, la suma de los grados de los vértices es igual al doble del número de aristas. [ 6 ] En grafos dirigidos , otra forma de la fórmula de suma de grados establece que la suma de los grados de entrada de todos los vértices y la suma de los grados de salida son iguales al número de aristas. Aquí, el grado de entrada es el número de aristas entrantes y el grado de salida es el número de aristas salientes. [ 7 ] Una versión de la fórmula de suma de grados también se aplica a familias finitas de conjuntos o, equivalentemente, a multigrafos : la suma de los grados de los elementos (donde el grado es igual al número de conjuntos que lo contienen) siempre es igual a la suma de las cardinalidades de los conjuntos. [ 8 ]

Ambos resultados también se aplican a cualquier subgrafo del grafo dado y, en particular, a sus componentes conexas . Una consecuencia es que, para cualquier vértice impar, debe existir un camino que lo conecte con otro vértice impar. [ 9 ]

Aplicaciones

Senderos y recorridos de Euler

Vista esquemática de los siete puentes de Königsberg.
Grafo con vértices para cada masa terrestre y una arista para cada puente.

Leonhard Euler demostró por primera vez el lema del apretón de manos en su trabajo sobre los Siete Puentes de Königsberg , donde planteaba la pregunta de cómo recorrer a pie la ciudad de Königsberg (actualmente Kaliningrado ) cruzando cada uno de sus siete puentes una sola vez. En términos de teoría de grafos, esto se traduce en la pregunta de cómo encontrar un camino euleriano o un recorrido euleriano en un grafo conexo que representa la ciudad y sus puentes: un recorrido a través del grafo que atraviesa cada arista una sola vez, terminando en un vértice diferente al de partida en el caso de un camino euleriano o regresando a su punto de partida en el caso de un recorrido euleriano. Euler enunció los resultados fundamentales de este problema en función del número de vértices impares del grafo, que el lema del apretón de manos restringe a un número par. Si este número es cero, existe un recorrido euleriano, y si es dos, existe un camino euleriano. En caso contrario, el problema no tiene solución. En el caso de los Siete Puentes de Königsberg, el grafo que representa el problema tiene cuatro vértices impares y no tiene ni un camino euleriano ni un recorrido euleriano. [ 3 ] Por lo tanto, era imposible recorrer los siete puentes de Königsberg sin repetir alguno.

En el algoritmo de Christofides-Serdyukov para aproximar el problema del viajante , las implicaciones geométricas de la fórmula de la suma de grados juegan un papel vital, permitiendo que el algoritmo conecte vértices en pares para construir un grafo en el que un recorrido de Euler forme un recorrido aproximado del TSP. [ 10 ]

enumeración combinatoria

Se puede demostrar que varias estructuras combinatorias tienen un número par relacionándolas con los vértices impares en un "grafo de intercambio" apropiado. [ 11 ]

Por ejemplo, como demostró CAB Smith , en cualquier gráfico cúbicoGRAMO{\displaystyle G}Debe haber un número par de ciclos hamiltonianos a través de cualquier borde fijo.túv{\displaystyle uv}Estos son ciclos que pasan por cada vértice exactamente una vez. Thomason (1978) utilizó una demostración basada en el lema del apretón de manos para extender este resultado a grafos en los que todos los vértices tienen grado impar. Thomason define un grafo de intercambio.H{\displaystyle H}, cuyos vértices están en correspondencia biunívoca con los caminos hamiltonianos enGRAMO{\displaystyle G}comenzando entú{\displaystyle u}y continuando a través del bordetúv{\displaystyle uv}Dos de esos caminospag1{\displaystyle p_{1}}ypag2{\displaystyle p_{2}}se definen como conectados por una arista enH{\displaystyle H}si uno puede obtenerpag2{\displaystyle p_{2}}agregando un nuevo borde al final depag1{\displaystyle p_{1}}y quitando otro borde del medio depag1{\displaystyle p_{1}}Esta operación es reversible, formando una relación simétrica , por lo tantoH{\displaystyle H}es un grafo no dirigido. Si la rutapag{\displaystyle p}termina en el vérticew{\displaystyle w}, entonces el vértice correspondiente apag{\displaystyle p}enH{\displaystyle H}tiene grado igual al número de maneras quepag{\displaystyle p}puede extenderse mediante una arista que no se conecta de nuevo atú{\displaystyle u}; es decir, el grado de este vértice enH{\displaystyle H}es ogrados⁡(w)−1{\displaystyle \deg(w)-1}(un número par) sipag{\displaystyle p}no forma parte de un ciclo hamiltoniano a través detúv{\displaystyle uv}, ogrados⁡(w)−2{\displaystyle \deg(w)-2}(un número impar) sipag{\displaystyle p}es parte de un ciclo hamiltoniano a través detúv{\displaystyle uv}. DesdeH{\displaystyle H}tiene un número par de vértices impares,GRAMO{\displaystyle G}debe tener un número par de ciclos hamiltonianos a través detúv{\displaystyle uv}. [ 12 ]

Otras aplicaciones

El lema del apretón de manos (o fórmula de la suma de grados) también se utiliza en demostraciones de otros resultados matemáticos. Entre ellos se incluyen los siguientes:

Un coloreado de Sperner de un triángulo triangulado, sombreado para resaltar los tres triángulos pequeños que tienen los tres colores de vértice.
  • El lema de Sperner establece que, si un triángulo grande se subdivide en triángulos más pequeños que se unen arista con arista, y los vértices se etiquetan con tres colores de manera que solo dos de los colores se utilicen a lo largo de cada arista del triángulo grande, entonces al menos uno de los triángulos más pequeños tiene vértices de los tres colores; tiene aplicaciones en teoremas de punto fijo , algoritmos de búsqueda de raíces y división justa . Una demostración de este lema forma un grafo de intercambio cuyos vértices son los triángulos (tanto pequeños como grandes) y cuyas aristas conectan pares de triángulos que comparten dos vértices de ciertos dos colores. El triángulo grande necesariamente tiene grado impar en este grafo de intercambio, al igual que un triángulo pequeño con los tres colores, pero no los otros triángulos pequeños. Por el lema del apretón de manos, debe haber un número impar de triángulos pequeños con los tres colores, y por lo tanto, debe existir al menos un triángulo de este tipo. [ 13 ]
El problema del alpinismo
  • El problema de la escalada de montaña establece que, para funciones suficientemente bien comportadas en un intervalo unitario , con valores iguales en los extremos del intervalo, es posible coordinar el movimiento de dos puntos, partiendo de extremos opuestos del intervalo, de manera que se encuentren en algún punto intermedio, manteniendo puntos de igual valor durante todo el movimiento. Una demostración de esto consiste en aproximar la función mediante una función lineal a trozos con los mismos puntos extremos, parametrizando la posición de los dos puntos móviles mediante las coordenadas de un único punto en el cuadrado unitario , y demostrando que las posiciones disponibles para los dos puntos forman un grafo finito, incrustado en este cuadrado, con solo la posición inicial y su reversa como vértices impares. Por el lema del apretón de manos, estas dos posiciones pertenecen al mismo componente conexo del grafo, y un camino de una a la otra necesariamente pasa por el punto de encuentro deseado. [ 14 ]
  • La conjetura de reconstrucción se refiere al problema de determinar de forma unívoca la estructura de un grafo a partir del multiconjunto de subgrafos formados al eliminar un único vértice. Con esta información, se puede utilizar la fórmula de suma de grados para recuperar el número de aristas del grafo dado y los grados de cada vértice. A partir de esto, es posible determinar si el grafo dado es regular y, de ser así, determinarlo de forma unívoca a partir de cualquier subgrafo al que se le haya eliminado un vértice, añadiendo un nuevo vecino a todos los vértices del subgrafo con grado demasiado bajo. Por lo tanto, todos los grafos regulares pueden reconstruirse. [ 15 ]
  • El juego de Hex se juega entre dos jugadores, quienes colocan piezas de su color en un tablero con forma de paralelogramo , recubierto con hexágonos, hasta que uno de ellos tenga un camino conectado de piezas adyacentes de un lado del tablero al otro. Nunca puede terminar en empate: cuando el tablero esté completamente lleno de piezas, uno de los jugadores habrá formado un camino ganador. Una prueba de esto consiste en un grafo a partir de un tablero lleno, con vértices en las esquinas de los hexágonos y aristas en los lados de los hexágonos que separan los colores de los dos jugadores. Este grafo tiene cuatro vértices impares en las esquinas del tablero y vértices pares en el resto, por lo que debe contener un camino que conecte dos esquinas, el cual necesariamente tiene un camino ganador para un jugador en uno de sus lados. [ 16 ]

Prueba

La demostración de Euler de la fórmula de la suma de grados utiliza la técnica del doble conteo : cuenta el número de pares incidentes.(v,mi){\displaystyle (v,e)}dóndemi{\displaystyle e}es una arista y un vérticev{\displaystyle v}es uno de sus extremos, de dos maneras diferentes. Vérticev{\displaystyle v}pertenece agrados⁡(v){\displaystyle \deg(v)}pares, dondegrados⁡(v){\displaystyle \deg(v)}(el grado dev{\displaystyle v}) es el número de aristas incidentes a ella. Por lo tanto, el número de pares incidentes es la suma de los grados. Sin embargo, cada arista en el grafo pertenece a exactamente dos pares incidentes, uno para cada uno de sus extremos; por lo tanto, el número de pares incidentes es2|mi|{\displaystyle 2|E|}Dado que estas dos fórmulas cuentan el mismo conjunto de objetos, deben tener valores iguales. La misma demostración puede interpretarse como la suma de las entradas de la matriz de incidencia del grafo de dos maneras: por filas para obtener la suma de los grados y por columnas para obtener el doble del número de aristas. [ 5 ]

Para los grafos, el lema del apretón de manos se deduce como corolario de la fórmula de la suma de grados. [ 8 ] En una suma de enteros, la paridad de la suma no se ve afectada por los términos pares en la suma; la suma total es par cuando hay un número par de términos impares, e impar cuando hay un número impar de términos impares. Dado que un lado de la fórmula de la suma de grados es el número par2|mi|{\displaystyle 2|E|}, la suma del otro lado debe tener un número par de términos impares; es decir, debe haber un número par de vértices de grado impar. [ 5 ]

Alternativamente, es posible utilizar la inducción matemática para demostrar la fórmula de la suma de grados, [ 2 ] o para demostrar directamente que el número de vértices de grado impar es par, eliminando una arista a la vez de un grafo dado y utilizando un análisis de casos sobre los grados de sus extremos para determinar el efecto de esta eliminación en la paridad del número de vértices de grado impar. [ 17 ]

En clases especiales de grafos

El grafo de Clebsch , regular de grado cinco, tiene un número par de vértices (16) y un número de aristas (40) que es un múltiplo de cinco.
El dodecaedro rómbico es biregular con seis vértices de grado cuatro y ocho vértices de grado tres; 6 × 4 = 8 × 3 = 24 , su número de aristas.

Gráficos regulares

La fórmula de suma de grados implica que cadar{\displaystyle r}- gráfico regular connorte{\displaystyle n}vértices tienenorter/2{\displaystyle nr/2}aristas. [ 18 ] Debido a que el número de aristas debe ser un número entero , se deduce que cuandor{\displaystyle r}es impar el número de vértices debe ser par. [ 19 ] Además, para valores impares der{\displaystyle r}, el número de aristas debe ser divisible porr{\displaystyle r}. [ 20 ]

Grafos bipartitos y biregulares

Un grafo bipartito tiene sus vértices divididos en dos subconjuntos, con cada arista teniendo un extremo en cada subconjunto. Del mismo argumento de doble conteo se deduce que, en cada subconjunto, la suma de los grados es igual al número de aristas en el grafo. En particular, ambos subconjuntos tienen sumas de grados iguales. [ 21 ] Para grafos biregulares , con una partición de los vértices en subconjuntosV1{\displaystyle V_{1}}yV2{\displaystyle V_{2}}con cada vértice en un subconjuntoVi{\displaystyle V_{i}}tener títulori{\displaystyle r_{i}}, debe ser el caso que|V1|r1=|V2|r2{\ Displaystyle | V_ {1} | r_ {1} = | V_ {2} | r_ {2}}; ambos son iguales al número de aristas. [ 22 ]

Grafos infinitos

Un grafo infinito con un único vértice impar.

El lema del apretón de manos no se aplica en su forma habitual a grafos infinitos, incluso cuando estos tienen solo un número finito de vértices de grado impar. Por ejemplo, un grafo de caminos infinitos con un solo extremo tiene un único vértice de grado impar, en lugar de un número par de dichos vértices. Sin embargo, es posible formular una versión del lema del apretón de manos utilizando el concepto de extremo , una clase de equivalencia de caminos semiinfinitos ("rayos") que considera dos rayos como equivalentes cuando existe un tercer rayo que utiliza infinitos vértices de cada uno de ellos. El grado de un extremo es el número máximo de rayos disjuntos por aristas que contiene, y un extremo es impar si su grado es finito e impar. De forma más general, es posible definir un extremo como impar o par, independientemente de si tiene grado infinito, en grafos para los que todos los vértices tienen grado finito. Entonces, en tales grafos, el número de vértices impares y extremos impares, sumados, es par o infinito. [ 23 ]

Subgrafos

Según un teorema de Gallai, los vértices de cualquier grafo pueden particionarse como:V=Vmi∪Vo{\displaystyle V=V_{e}\cup V_{o}}donde en los dos subgrafos inducidos resultantes ,GRAMO[Vmi]{\displaystyle G[V_{e}]}tiene todos los títulos iguales yGRAMO[Vo]{\displaystyle G[V_{o}]}tiene todos los grados impares. Aquí,|Vo|{\displaystyle |V_{o}|}debe ser par por el lema del apretón de manos. También es posible encontrar subgrafos inducidos de grado par e impar con muchos vértices. Se puede encontrar un subgrafo inducido de grado par con al menos la mitad de los vértices, y se puede encontrar un subgrafo inducido de grado impar (en un grafo sin vértices aislados ) con|Vo|/|V|>1/10000{\displaystyle |V_{o}|/|V|>1/10000}. [ 24 ] [ 25 ]

Complejidad computacional

En relación con el método del grafo de intercambio para demostrar la existencia de estructuras combinatorias, resulta interesante preguntarse con qué eficiencia se pueden encontrar dichas estructuras. Por ejemplo, supongamos que se nos da como entrada un ciclo hamiltoniano en un grafo cúbico; del teorema de Smith se deduce que existe un segundo ciclo. ¿Con qué rapidez se puede encontrar este segundo ciclo? Papadimitriou (1994) investigó la complejidad computacional de cuestiones como esta, o más generalmente, de encontrar un segundo vértice de grado impar cuando se nos da un único vértice impar en un grafo grande definido implícitamente . Definió la clase de complejidad PPA para englobar problemas como este; [ 26 ] una clase estrechamente relacionada, definida en grafos dirigidos, PPAD , ha atraído una atención significativa en la teoría de juegos algorítmica porque el cálculo de un equilibrio de Nash es computacionalmente equivalente a los problemas más difíciles de esta clase. [ 27 ]

Los problemas computacionales que se ha demostrado que son completos para la clase de complejidad PPA incluyen tareas computacionales relacionadas con el lema de Sperner [ 28 ] y con la subdivisión justa de recursos según el teorema de Hobby-Rice . [ 29 ]

Notas

  1. 1 2 Hein, James L. (2015), "Ejemplo 3: El problema del apretón de manos" , Estructuras discretas, lógica y computabilidad , Jones & Bartlett Publishers, pág.  703, ISBN 9781284070408
  2. 1 2 3 Gunderson, David S. (2014), Manual de inducción matemática: teoría y aplicaciones , CRC Press, pág. 240, ISBN  9781420093650
  3. ^ Euler , L. ( 1736), "Solutio problematis ad geometriam situs pertinentis" , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128-140Reimpreso y traducido en Biggs, NL ; Lloyd, EK; Wilson, RJ (1976), Graph Theory 1736–1936 , Oxford University Press
  4. 1 2 Higgins, Peter M. (1998), Matemáticas para los curiosos , Oxford University Press, pág. 201, ISBN  9780192880727
  5. 1 2 3 Biggs, Norman L. (2002), "15.3: Grado" , Matemáticas Discretas , Oxford University Press, págs. 181–182 , ISBN  9780198507178
  6. ↑ West, Douglas B. (1996), "1.3.3. Teorema. (Fórmula de la suma de grados)", Introducción a la teoría de grafos (2.ª ed.), Prentice Hall, pág. 26, ISBN   9780132278287
  7. ↑ Loehr, Nicholas (2011), "3.31. Teorema: Fórmula de suma de grados para digrafos" , Combinatoria biyectiva , CRC Press, pág. 106, ISBN  9781439848869
  8. 1 2 Jukna, Stasys (2011), "Proposición 1.7", Combinatoria extremal , Textos en informática teórica. Una serie EATCS, Springer, pág. 9, doi : 10.1007/978-3-642-17364-6 , ISBN  978-3-642-17363-9
  9. ↑ Ray, Santanu Saha (2012), "Teorema 2.2", Teoría de grafos con algoritmos y sus aplicaciones en ciencia y tecnología aplicadas , Springer, pág. 16, ISBN  9788132207504
  10. ↑Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem(PDF), Report 388, Graduate School of Industrial Administration, CMU, archived(PDF) from the original on 2019-07-21. The handshaking lemma is cited at the top of page 2.
  11. ↑Cameron, Kathie; Edmonds, Jack (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier, 49 (3): 815–827, doi:10.5802/aif.1694, MR 1703426
  12. ↑Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 978-0-7204-0843-0, MR 0499124
  13. ↑Aigner, Martin; Ziegler, Günter M. (2018), "Section 28.6: Sperner's Lemma", Proofs from THE BOOK (6th ed.), Berlin: Springer, pp. 203–205, doi:10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, MR 3823190
  14. ↑Goodman, Jacob E.; Pach, János; Yap, Chee-K. (1989), "Mountain climbing, ladder moving, and the ring-width of a polygon"(PDF), The American Mathematical Monthly, 96 (6): 494–510, doi:10.2307/2323971, JSTOR 2323971, MR 0999412
  15. ↑Lauri, Josef; Scapellato, Raffaele (2016), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Lecture Note Series, vol. 432 (2nd ed.), Cambridge University Press, pp. 105–106, doi:10.1017/CBO9781316669846, ISBN 978-1-316-61044-2, MR 3496604
  16. ↑Gale, David (1979), "The game of Hex and the Brouwer fixed-point theorem", The American Mathematical Monthly, 86 (10): 818–827, doi:10.1080/00029890.1979.11994922, JSTOR 2320146, MR 0551501
  17. ↑ Neto, Antonio Caminha Muniz (2018), Una excursión por las matemáticas elementales, Volumen III: Matemáticas discretas y álgebra polinomial , Problem Books in Mathematics, Springer, pp. 132 , 562 , ISBN  9783319779775
  18. ↑ Aldous, Joan M.; Wilson, Robin J. (2000), "Teorema 2.2" , Gráficos y aplicaciones: un enfoque introductorio , Serie de matemáticas para estudiantes de pregrado, The Open University, Springer-Verlag, pág. 44 , ISBN  978-1-85233-259-4
  19. ↑ Wallis, WD (2011), "Sección 7.1, Introducción a los gráficos, Corolario 1" , Guía para principiantes de matemáticas discretas (2.ª ed.), Springer, pág. 219, ISBN   9780817682866
  20. ↑ Clark, John; Holton, Derek Allan (1995), "Problema 1.4.6" , A First Look at Graph Theory , Allied Publishers, pág. 16, ISBN  9788170234630
  21. ^ Lovász, László (2014), Problemas y ejercicios combinatorios (2ª ed.), Elsevier, p. 281, ISBN   9780080933092
  22. ↑ Pisanski, Tomaž ; Servatius, Brigitte (2013), "2.3.4: Gráficos bipartitos semirregulares" , Configuraciones desde un punto de vista gráfico , Textos avanzados de Birkhäuser: Basler Lehrbücher, Nueva York: Birkhäuser/Springer, p. 35, doi : 10.1007/978-0-8176-8364-1 , ISBN  978-0-8176-8363-4, MR 2978043 
  23. ↑ Bruhn, Henning; Stein, Maya (2007), "Sobre grados finales y ciclos infinitos en grafos localmente finitos", Combinatorica , 27 (3): 269– 291, doi : 10.1007/s00493-007-2149-0 , MR 2345811 , S2CID 8367713  ; véase la Proposición 15, pág. 284
  24. ↑ Ferber, Asaf; Krivelevich, Michael (2022), "Cada grafo contiene un subgrafo inducido de tamaño lineal con todos los grados impares", Advances in Mathematics , 406 108534, arXiv : 2009.05495 , doi : 10.1016/j.aim.2022.108534 , MR 4448268 
  25. ↑ Honner, Patrick (24 de marzo de 2022), "Lo que un juego de matemáticas nos revela sobre la teoría de grafos" , Quanta , consultado el 27 de marzo de 2022.
  26. ↑ Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia", Journal of Computer and System Sciences , 48 ​​(3): 498– 532, doi : 10.1016/S0022-0000(05)80063-7 , MR 1279412 
  27. ↑ Chen, Xi ; Deng, Xiaotie (2006), "Resolviendo la complejidad del equilibrio de Nash de dos jugadores", Actas del 47.º Simposio sobre Fundamentos de la Informática , págs. 261–271 , doi : 10.1109/FOCS.2006.69 , ISBN  0-7695-2720-5, S2CID 14102058 , ECCC TR05-140  
  28. ↑ Grigni, Michelangelo (2001), "Un lema de Sperner completo para PPA", Information Processing Letters , 77 ( 5–6 ): 255–259 , doi : 10.1016/S0020-0190(00)00152-6 , MR 1818525 
  29. ↑ Filos-Ratsikas, Aris; Goldberg, Paul W. (2018), "Consensus halving is PPA-complete", en Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pp. 51– 64, arXiv : 1711.04503 , doi : 10.1145/3188745.3188880 , ISBN  978-1-4503-5559-9, S2CID 8111195