Un torneo es un gráfico dirigido (dígrafo) que se obtiene asignando una dirección para cada borde en un gráfico completo no dirigido . Es decir, es una orientación de un gráfico completo, o equivalentemente un gráfico dirigido en el que cada par de vértices distintos está conectado por un borde dirigido (a menudo, llamado arco ) con cualquiera de las dos posibles orientaciones.
Torneo | |
---|---|
Vértices | |
Bordes | |
Tabla de gráficos y parámetros |
Landau (1953) investigó por primera vez muchas de las propiedades importantes de los torneos para modelar las relaciones de dominancia en las bandadas de pollos. Las aplicaciones actuales de los torneos incluyen el estudio de la teoría del voto y la teoría de la elección social, entre otras cosas.
El nombre torneo se origina a partir de la interpretación de un gráfico como el resultado de un torneo de todos contra todos en el que cada jugador se encuentra con todos los demás jugadores exactamente una vez y en el que no se producen empates. En el dígrafo del torneo, los vértices corresponden a los jugadores. La ventaja entre cada par de jugadores está orientada del ganador al perdedor. Si jugador vence al jugador , entonces se dice que domina . Si cada jugador vence al mismo número de otros jugadores ( indegree = outdegree ), el torneo se llama regular .
Caminos y ciclos
Teorema : cualquier torneo en un número finitode vértices contiene un camino hamiltoniano , es decir, un camino dirigido en todos losvértices ( Rédei 1934).
Esto se demuestra fácilmente por inducción en: supongamos que la declaración es válida para y considere cualquier torneo en vértices. Elige un vértice de y considera un camino dirigido en . Hay algunos tal que . (Una posibilidad es dejar ser máximo de tal manera que para cada . Alternativamente, deje ser mínimo tal que .)
es un camino dirigido como se desee. Este argumento también proporciona un algoritmo para encontrar el camino hamiltoniano. Algoritmos más eficientes, que solo requieren examinarde los bordes, se conocen. [1]
Otro resultado básico de los torneos es que cada torneo fuertemente conectado tiene un ciclo hamiltoniano (Camion 1959). Más fuertemente, cada torneo fuertemente conectado es un vértice pancíclico : para cada vértice, y cada en el rango de tres al número de vértices en el torneo, hay un ciclo de duración conteniendo . [2] Un torneoes -fuertemente conectado si para cada set de vértices de , está fuertemente conectado. Si el torneo está fuertemente conectado a 4, entonces cada par de vértices puede conectarse con un camino hamiltoniano (Thomassen 1980). Para cada set de como máximo arcos de un -torneo fuertemente conectado , tenemos eso tiene un ciclo hamiltoniano [3] Este resultado se amplió en [4]
Transitividad
Un torneo en el que y se llama transitivo . En otras palabras, en un torneo transitivo, los vértices pueden estar (estrictamente) totalmente ordenados por la relación del borde, y la relación del borde es lo mismo que la accesibilidad .
Condiciones equivalentes
Las siguientes declaraciones son equivalentes para un torneo en vértices:
- es transitivo.
- es un pedido total estricto.
- es acíclico .
- no contiene un ciclo de duración 3.
- La secuencia de puntuación (conjunto de grados externos) de es .
- tiene exactamente un camino hamiltoniano.
Teoría de Ramsey
Los torneos transitivos juegan un papel en la teoría de Ramsey análogo al de las camarillas en los gráficos no dirigidos. En particular, todos los torneos de vértices contiene un subtorneo transitivo en vértices. [5] La demostración es simple: elige cualquier vértice formar parte de este sub-torneo, y formar el resto del sub-torneo de forma recursiva en el conjunto de vecinos entrantes de o el conjunto de vecinos salientes de , el que sea más grande. Por ejemplo, cada torneo de siete vértices contiene un subtorneo transitivo de tres vértices; el torneo de Paley en siete vértices muestra que esto es lo máximo que se puede garantizar ( Erdős & Moser 1964 ). Sin embargo, Reid y Parker (1970) demostraron que este límite no es estrecho para algunos valores mayores de .
Erdős y Moser (1964) demostraron que hay torneos en vértices sin un subtorneo transitivo de tamaño Su demostración utiliza un argumento de conteo : el número de formas en que un-El torneo transitivo de elementos puede ocurrir como un sub-torneo de un torneo más grande en vértices etiquetados es
y cuando Es mas grande 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.
Torneos paradójicos
Un jugador que gane todos los juegos, naturalmente, será el ganador del torneo. Sin embargo, como muestra 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 llama -paradójico si por cada -subconjunto de elementos de hay un vértice en tal que para todos . Por medio del método probabilístico , Paul Erdős mostró que para cualquier valor fijo de, Si , luego casi todos los torneos en es -paradójico. [6] Por otro lado, un argumento sencillo muestra que cualquier-El torneo paradójico debe tener al menos jugadores, que se mejoró para por Esther y George Szekeres (1965). [7] Hay una construcción explícita de-Torneos paradójicos con jugadores de Graham y Spencer (1971) a saber, el torneo Paley .
Condensación
La condensación de cualquier torneo es en sí misma un torneo transitivo. Por lo tanto, incluso para los torneos que no son transitivos, los componentes fuertemente conectados del torneo pueden estar totalmente ordenados. [8]
Secuencias de puntajes y conjuntos de puntajes
La secuencia de puntuación de un torneo es la secuencia no decreciente de grados externos de los vértices de un torneo. El conjunto de puntuaciones de un torneo es el conjunto de números enteros que son los grados externos de los vértices de ese torneo.
Teorema de Landau (1953) Una secuencia no decreciente de enteros es una secuencia de puntuación si y solo si:
Dejar ser el número de secuencias de puntuación diferentes de tamaño . La secuencia(secuencia A000571 en la OEIS ) comienza como:
1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...
Winston y Kleitman demostraron que para n suficientemente grandes :
dónde Takács demostró más tarde, utilizando algunas suposiciones razonables pero no probadas, que
dónde
Juntos, estos proporcionan evidencia de que:
Aquí significa un límite asintóticamente estrecho .
Yao demostró que cada conjunto no vacío de enteros no negativos es la puntuación establecida para algún torneo.
Relaciones mayoritarias
En la teoría de la elección social , los torneos surgen naturalmente como relaciones mayoritarias de perfiles de preferencia. [9] Deja ser un conjunto finito de alternativas y considerar una lista de órdenes lineales sobre. Interpretamos cada pedidocomo la clasificación de preferencia de un votante. La (estricta) relación mayoritaria de encima luego se define de modo que si y solo si la mayoría de los votantes prefiere a , es decir . Si el numero de votantes es impar, entonces la relación de mayoría forma la relación de predominio de un torneo en un conjunto de vértices .
Según un lema de McGarvey, cada torneo en vértices se pueden obtener como la relación mayoritaria de como máximo votantes. [9] [10] Los resultados de Stearns y Erdős & Moser establecieron posteriormente que los votantes son necesarios para inducir todos los torneos en vértices. [11]
Laslier (1997) estudia en qué sentido un conjunto de vértices puede denominarse el conjunto de "ganadores" de un torneo. Esto se reveló útil en Ciencias Políticas para estudiar, en modelos formales de economía política, lo que puede ser el resultado de un proceso democrático. [12]
Ver también
- Gráfico orientado
- Torneo Paley
- Conjetura de Sumner
- Solución de torneo
Notas
- ^ Bar-Noy y Naor (1990) .
- ^ Luna (1966) , Teorema 1.
- ^ Fraisse y Thomassen (1987) .
- ^ Bang-Jensen, Gutin y Yeo (1997) .
- ^ Erdős y Moser (1964) .
- ↑ Erdős (1963)
- ^ Szekeres, E .; Szekeres, G. (1965). "Sobre un problema de Schütte y Erdős". Matemáticas. Gaz . 49 : 290-293.
- ^ Harary y Moser (1966) , Corolario 5b.
- ^ a b Brandt, Felix y Brill, Markus y Harrenstein, Paul, "Soluciones de torneo". Capítulo 3 en: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional . Prensa de la Universidad de Cambridge. ISBN 9781107060432.( versión gratuita en línea )
- ^ McGarvey, David C. (1953). "Un teorema sobre la construcción de paradojas del voto". Econometrica . 21 (4): 608–610. doi : 10.2307 / 1907926 . JSTOR 1907926 .
- ^ Stearns, Richard (1959). "El problema de la votación". The American Mathematical Monthly . 66 (9): 761–763. doi : 10.2307 / 2310461 . JSTOR 2310461 .
- ^ Austen-Smith, D. y J. Banks, teoría política positiva, 1999, The University of Michigan Press.
Referencias
- 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), "Clasificación, conjuntos de retroalimentación mínima y trayectorias de Hamilton en los torneos", SIAM Journal on Discrete Mathematics , 3 (1): 7-20, doi : 10.1137 / 0403002.
- Camion, Paul (1959), "Chemins et circuits 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. Akad. Estera. Kutató Int. Közl. , 9 : 125-132, MR 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 round robin", American Mathematical Monthly , 73 (3): 231–246, doi : 10.2307 / 2315334 , JSTOR 2315334.
- 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 Biphysics , 15 (2): 143-148, doi : 10.1007 / BF02476378.
- Laslier, J.-F. (1997), Soluciones para torneos y votación mayoritaria , Springer.
- Moon, JW (1966), "Sobre los sub-torneos 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), "Rechazo de una conjetura de Erdös y Moser", Journal of Combinatorial Theory , 9 (3): 225-238, doi : 10.1016 / S0021-9800 (70) 80061-8.
- Szekeres, 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 , Applied Probability Trust, 23 (3): 557–585, doi : 10.2307 / 1427622 , JSTOR 1427622.
- Thomassen, Carsten (1980), "Torneos conectados con Hamilton", 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. Toro. , 34 : 804–808.
Este artículo incorpora material del torneo en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .