Torneo (teoría de grafos)

Grafo dirigido donde cada par de vértices tiene un arco

En teoría de grafos , un torneo es un grafo dirigido con exactamente una arista entre cada dos vértices , en una de las dos direcciones posibles. Equivalentemente, un torneo es una orientación de un grafo completo no dirigido . (Sin embargo, como grafos dirigidos, los torneos no son completos: los grafos dirigidos completos tienen dos aristas, en ambas direcciones, entre cada dos vértices. ^[1] ) El nombre torneo proviene de interpretar el grafo como el resultado de un torneo de todos contra todos , un juego donde cada jugador se empareja contra todos los demás exactamente una vez. En un torneo, los vértices representan a los jugadores y las aristas entre los jugadores apuntan del ganador al perdedor.

Muchas de las propiedades importantes de los torneos fueron investigadas por HG Landau en 1953 para modelar las relaciones de dominio en bandadas de pollos. ^[2] Los torneos también se estudian en profundidad en la teoría de la votación , donde pueden representar información parcial sobre las preferencias de los votantes entre múltiples candidatos, y son fundamentales para la definición de los métodos de Condorcet .

Si cada jugador vence al mismo número de otros jugadores ( grado de entrada − grado de salida = 0) el torneo se denomina regular .

Caminos y ciclos

a se inserta entre v ₂ y v ₃ .

Cualquier torneo sobre un número finito de vértices contiene un camino hamiltoniano , es decir, un camino dirigido sobre todos los vértices ( Rédei 1934). ${\displaystyle n}$ ${\displaystyle n}$

Esto se demuestra fácilmente por inducción en : supongamos que la afirmación es válida para , y consideremos cualquier torneo en vértices. Elijamos un vértice de y consideremos un camino dirigido en . Existe alguno tal que . (Una posibilidad es dejar que sea máximo tal que para cada . Alternativamente, sea mínimo tal que .) es un camino dirigido como se desea. Este argumento también proporciona un algoritmo para encontrar el camino hamiltoniano. Se conocen algoritmos más eficientes, que requieren examinar solo los bordes. Los caminos hamiltonianos están en correspondencia uno a uno con los conjuntos de arcos de retroalimentación mínimos del torneo. ^[3] El teorema de Rédei es el caso especial para grafos completos del teorema de Gallai–Hasse–Roy–Vitaver , que relaciona las longitudes de los caminos en las orientaciones de los grafos con el número cromático de estos grafos. ^[4] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle n+1}$ ${\displaystyle v_{0}}$ ${\displaystyle T}$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ ${\displaystyle T\smallsetminus \{v_{0}\}}$ ${\displaystyle i\in \{0,\ldots ,n\}}$ ${\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)}$ ${\displaystyle i\in \{0,\ldots ,n\}}$ ${\displaystyle j\leq i,v_{j}\rightarrow v_{0}}$ ${\displaystyle i}$ ${\displaystyle \forall j>i,v_{0}\rightarrow v_{j}}$ $${\displaystyle v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}}$$ ${\displaystyle O(n\log n)}$

Otro resultado básico sobre los torneos es que cada torneo fuertemente conectado tiene un ciclo hamiltoniano . ^[5] Más fuertemente, cada torneo fuertemente conectado es pancíclico de vértices : para cada vértice , y cada uno en el rango de tres al número de vértices en el torneo, hay un ciclo de longitud que contiene . ^[6] Un torneo es -fuertemente conectado si para cada conjunto de vértices de , está fuertemente conectado. Si el torneo es 4‑fuertemente conectado, entonces cada par de vértices puede estar conectado con un camino hamiltoniano. ^[7] Para cada conjunto de como máximo arcos de un torneo -fuertemente conectado , tenemos que tiene un ciclo hamiltoniano. ^[8] Este resultado fue extendido por Bang-Jensen, Gutin y Yeo (1997). ^[9] ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle U}$ ${\displaystyle k-1}$ ${\displaystyle T}$ ${\displaystyle T-U}$ ${\displaystyle B}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle T-B}$

Transitividad

Un torneo transitivo en 8 vértices.

Un torneo en el que y se denomina transitivo . En otras palabras, en un torneo transitivo, los vértices pueden estar (estrictamente) totalmente ordenados por la relación de aristas, y la relación de aristas es la misma que la alcanzabilidad . ${\displaystyle ((a\rightarrow b)}$ ${\displaystyle (b\rightarrow c))}$ ${\displaystyle \Rightarrow }$ ${\displaystyle (a\rightarrow c)}$

Condiciones equivalentes

Las siguientes afirmaciones son equivalentes para un torneo en vértices: ${\displaystyle T}$ ${\displaystyle n}$

1. ${\displaystyle T}$es transitivo
2. ${\displaystyle T}$Es un ordenamiento total estricto.
3. ${\displaystyle T}$es acíclico .
4. ${\displaystyle T}$no contiene un ciclo de longitud 3.
5. La secuencia de puntuación (conjunto de grados de salida) de es . ${\displaystyle T}$ ${\displaystyle \{0,1,2,\ldots ,n-1\}}$
6. ${\displaystyle T}$tiene exactamente un camino hamiltoniano.

Teoría de Ramsey

Los torneos transitivos desempeñan un papel en la teoría de Ramsey análogo al de las camarillas en grafos no dirigidos. En particular, cada torneo sobre vértices contiene un subtorneo transitivo sobre vértices. La prueba es sencilla: se elige un vértice cualquiera para que forme parte de este subtorneo y se forma el resto del subtorneo recursivamente sobre el conjunto de vecinos entrantes de o sobre el conjunto de vecinos salientes de , el que sea mayor. Por ejemplo, cada torneo sobre siete vértices contiene un subtorneo transitivo de tres vértices; el torneo de Paley sobre siete vértices muestra que esto es lo máximo que se puede garantizar. ^[10] Sin embargo, Reid y Parker (1970) demostraron que este límite no es estricto para algunos valores mayores de  . ^[11] ${\displaystyle n}$ ${\displaystyle 1+\lfloor \log _{2}n\rfloor }$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle n}$

Erdős y Moser (1964) demostraron que hay torneos en vértices sin un subtorneo transitivo de tamaño Su prueba utiliza un argumento de conteo : el número de formas en que un torneo transitivo de -elemento puede ocurrir como un subtorneo de un torneo más grande en vértices etiquetados es y cuando es mayor que , este número es demasiado pequeño para permitir la ocurrencia de un torneo transitivo dentro de cada uno de los diferentes torneos en el mismo conjunto de vértices etiquetados. ^[10] ${\displaystyle n}$ ${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$ ${\displaystyle k}$ ${\displaystyle n}$ $${\displaystyle {\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},}$$ ${\displaystyle k}$ ${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$ ${\displaystyle 2^{\binom {n}{2}}}$ ${\displaystyle n}$

Torneos paradójicos

Un jugador que gana todos los juegos sería naturalmente el ganador del torneo. Sin embargo, como lo demuestra la existencia de torneos no transitivos, puede que no exista tal jugador. Un torneo en el que cada jugador pierde al menos un juego se denomina torneo 1-paradójico. De manera más general, un torneo se denomina -paradójico si para cada subconjunto de -elementos de hay un vértice en tal que para todos los . Mediante el método probabilístico , Paul Erdős demostró que para cualquier valor fijo de , si , entonces casi todos los torneos en son -paradójicos. ^[12] Por otro lado, un argumento fácil muestra que cualquier torneo -paradójico debe tener al menos jugadores, lo que fue mejorado por Esther y George Szekeres en 1965. ^[13] Existe una construcción explícita de torneos -paradójicos con jugadores por Graham y Spencer (1971), a saber, el torneo Paley . ${\displaystyle T=(V,E)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle V}$ ${\displaystyle v_{0}}$ ${\displaystyle V\setminus S}$ ${\displaystyle v_{0}\rightarrow v}$ ${\displaystyle v\in S}$ ${\displaystyle k}$ ${\displaystyle |V|\geq k^{2}2^{k}\ln(2+o(1))}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2^{k+1}-1}$ ${\displaystyle (k+2)2^{k-1}-1}$ ${\displaystyle k}$ ${\displaystyle k^{2}4^{k-1}(1+o(1))}$

Condensación

La condensación de cualquier torneo es en sí misma un torneo transitivo. Por lo tanto, incluso en el caso de torneos que no son transitivos, los componentes fuertemente conectados del torneo pueden estar totalmente ordenados. ^[14]

Secuencias de puntuaciones y conjuntos de puntuaciones

La secuencia de puntajes de un torneo es la secuencia no decreciente de los grados de salida de los vértices de un torneo. El conjunto de puntajes de un torneo es el conjunto de números enteros que son los grados de salida de los vértices de ese torneo.

Teorema de Landau (1953) Una secuencia no decreciente de números enteros es una secuencia de puntuaciones si y sólo si: ^[2] ${\displaystyle (s_{1},s_{2},\ldots ,s_{n})}$

1. ${\displaystyle 0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}}$
2. ${\displaystyle s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\text{ for }}i=1,2,\ldots ,n-1}$
3. ${\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}$

Sea el número de secuencias de puntuaciones diferentes de tamaño . La secuencia (secuencia A000571 en la OEIS ) comienza como: ${\displaystyle s(n)}$ ${\displaystyle n}$ ${\displaystyle s(n)}$

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

Winston y Kleitman demostraron que para n suficientemente grande :

${\displaystyle s(n)>c_{1}4^{n}n^{-5/2},}$

donde Takács demostró más tarde, utilizando algunas suposiciones razonables pero no probadas, que ${\displaystyle c_{1}=0.049.}$

${\displaystyle s(n)<c_{2}4^{n}n^{-5/2},}$

donde ^[15] ${\displaystyle c_{2}<4.858.}$

En conjunto, estos datos proporcionan evidencia de que:

${\displaystyle s(n)\in \Theta (4^{n}n^{-5/2}).}$

Aquí significa un límite asintóticamente estrecho . ${\displaystyle \Theta }$

Yao demostró que cada conjunto no vacío de números enteros no negativos es el conjunto de puntajes para algún torneo. ^[16]

Relaciones mayoritarias

En la teoría de la elección social , los torneos surgen naturalmente como relaciones mayoritarias de perfiles de preferencia. ^[17] Sea un conjunto finito de alternativas y considere una lista de órdenes lineales sobre . Interpretamos cada orden como la clasificación de preferencia de un votante . La relación mayoritaria (estricta) de sobre se define entonces de modo que si y solo si una mayoría de los votantes prefiere , es decir . Si el número de votantes es impar, entonces la relación mayoritaria forma la relación de dominancia de un torneo en el conjunto de vértices . ${\displaystyle A}$ ${\displaystyle P=(\succ _{1},\dots ,\succ _{n})}$ ${\displaystyle A}$ ${\displaystyle \succ _{i}}$ ${\displaystyle i}$ ${\displaystyle \succ _{\text{maj}}}$ ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle a\succ _{\text{maj}}b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle |\{i\in [n]:a\succ _{i}b\}|>|\{i\in [n]:b\succ _{i}a\}|}$ ${\displaystyle n}$ ${\displaystyle A}$

Por un lema de McGarvey, cada torneo sobre vértices puede obtenerse como la relación mayoritaria de como máximo votantes. ^[18] Los resultados de Stearns y Erdős & Moser establecieron posteriormente que se necesitan votantes para inducir cada torneo sobre vértices. ^[19] ${\displaystyle m}$ ${\displaystyle m(m-1)}$ ${\displaystyle \Theta (m/\log m)}$ ${\displaystyle m}$

Laslier (1997) estudia en qué sentido un conjunto de vértices puede ser llamado el conjunto de “ganadores” de un torneo. ^[20] Esto se ha revelado útil en Ciencia Política para estudiar, en modelos formales de economía política, cuál puede ser el resultado de un proceso democrático. ^[21]

Véase también

• Gráfico orientado
• Torneo de Paley
• Conjetura de Sumner
• Solución de torneo

Notas

1. Weisstein, Eric W. , "Torneo", MathWorld
2. Landau (1953).
3. Bar-Noy y Naor (1990).
4. Havet (2013).
5. Camión (1959).
6. Luna (1966), Teorema 1.
7. Thomassen (1980).
8. Fraisse y Thomassen (1987).
9. Bang-Jensen, Gutin y Yeo (1997).
10. Erdős y Moser (1964).
11. Reid y Parker (1970).
12. Erdös (1963)
13. Szekeres y Szekeres (1965).
14. Harary y Moser (1966), Corolario 5b.
15. Takács (1991).
16. "El hombre que se ha enamorado de mí" (1989).
17. Brandt, Brill y Harrenstein (2016).
18. McGarvey (1953); Brandt, Brill y Harrenstein (2016)
19. Stearns (1959); Erdős y Moser (1964)
20. Laslier (1997).
21. Austen-Smith y Banks (1999).

Referencias

• Austen-Smith, D.; Banks, J. (1999), Teoría política positiva , University of Michigan Press
• Bang-Jensen, J.; Gutin, G .; Yeo, A. (1997), "Ciclos hamiltonianos que evitan arcos prescritos en torneos", Combinatoria, probabilidad y computación , 6 : 255–261
• Bar-Noy, A.; Naor, J. (1990), "Ordenamiento, conjuntos de retroalimentación mínima y caminos de Hamilton en torneos", SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi :10.1137/0403002
• Brandt, Félix; Genial, Markus; Harrenstein, Paul (2016), "Capítulo 3: Soluciones para torneos", en Brandt, Felix; Conitzer, Vicente; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (eds.), Manual de elección social computacional , Cambridge University Press, ISBN 9781107060432
• Camion, Paul (1959), "Chemins et circuitos hamiltoniens des graphes complets", Comptes Rendus de l'Académie des Sciences de Paris (en francés), 249 : 2151–2152
• Erdős, P. (1963), "Sobre un problema en la teoría de grafos" (PDF) , The Mathematical Gazette , 47 : 220–223, JSTOR  3613396, MR  0159319
• Erdős, P .; Moser, L. (1964), "Sobre la representación de grafos dirigidos como uniones de ordenamientos" (PDF) , Magyar Tud. Akád. Estera. Aeropuerto Internacional de Kutató. Kozl. , 9 : 125–132, SEÑOR  0168494
• Fraisse, P.; Thomassen, C. (1987), "Una solución constructiva a un problema de torneo", Graphs and Combinatorics , 3 : 239–250.
• Graham, RL ; Spencer, JH (1971), "Una solución constructiva a un problema de torneo", Canadian Mathematical Bulletin , 14 : 45–48, doi :10.4153/cmb-1971-007-1, MR  0292715.
• Harary, Frank ; Moser, Leo (1966), "La teoría de los torneos de todos contra todos", American Mathematical Monthly , 73 (3): 231–246, doi :10.2307/2315334, JSTOR  2315334.
• Havet, Frédéric (2013), "Sección 3.1: Teorema de Gallai-Roy y resultados relacionados" (PDF) , Orientaciones y coloración de gráficos , Apuntes de la escuela de verano SGT 2013 en Oléron, Francia, pp. 15–19
• Landau, HG (1953), "Sobre las relaciones de dominancia y la estructura de las sociedades animales. III. La condición para una estructura de puntuación", Bulletin of Mathematical Biophysics , 15 (2): 143–148, doi :10.1007/BF02476378.
• Laslier, J.-F. (1997), Soluciones de torneo y votación por mayoría , Springer
• McGarvey, David C. (1953), "Un teorema sobre la construcción de paradojas de votación", Econometrica , 21 (4): 608–610, doi :10.2307/1907926, JSTOR  1907926
• Moon, JW (1966), "Sobre los subtorneos de un torneo", Canadian Mathematical Bulletin , 9 (3): 297–301, doi : 10.4153/CMB-1966-038-7.
• Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged , 7 : 39–43.
• Reid, KB; Parker, ET (1970), "Refutación de una conjetura de Erdös y Moser", Journal of Combinatorial Theory , 9 (3): 225–238, doi : 10.1016/S0021-9800(70)80061-8
• Stearns, Richard (1959), "El problema de la votación", The American Mathematical Monthly , 66 (9): 761–763, doi :10.2307/2310461, JSTOR  2310461
• Székeres, E .; Szekeres, G. (1965), "Sobre un problema de Schütte y Erdős", The Mathematical Gazette , 49 : 290–293, doi :10.2307/3612854, MR  0186566.
• Takács, Lajos (1991), "Una excursión de Bernoulli y sus diversas aplicaciones", Advances in Applied Probability , 23 (3), Applied Probability Trust: 557–585, doi :10.2307/1427622, ​​JSTOR  1427622.
• Thomassen, Carsten (1980), "Torneos con conexión hamiltoniana", Journal of Combinatorial Theory , Serie B, 28 (2): 142–163, doi : 10.1016/0095-8956(80)90061-1.
• Yao, TX (1989), "Sobre la conjetura de Reid de conjuntos de puntuaciones para torneos", Chinese Sci. Bull. , 34 : 804–808.

Este artículo incorpora material del torneo en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .