Torneo (teoría de grafos)

Un torneo es un grafo dirigido que se obtiene a partir de un grafo completo no dirigido asignando una dirección a cada arista. Así, un torneo es un dígrafo en el que cada par de vértices está conectado por un solo arco dirigido.

Muchas propiedades importantes de los torneos son consideradas por Landau [ 1] para investigar el patrón de dominancia de pollitos en una parvada. Las aplicaciones actuales de los torneos incluyen la investigación sobre la votación y la elección colectiva entre otras cosas. El nombre del torneo proviene de una interpretación gráfica de los resultados de un torneo de todos contra todos, en el que cada jugador se enfrenta a todos los demás jugadores exactamente una vez y en el que no puede haber empates . En el dígrafo del torneo, los vértices corresponden a los jugadores. El arco entre cada par de jugadores está orientado de ganador a perdedor. Si el jugador vence al jugador , entonces se dice que domina . $a$ $b$ $a$ $b$

Caminos y ciclos

Cualquier torneo con un número finito de vértices contiene un camino hamiltoniano , es decir, un camino dirigido que contiene todos los vértices [2] . Esto se puede demostrar fácilmente por inducción matemática sobre : sea cierto el enunciado para , y sea cierto el torneo con vértices. Elijamos un vértice en y sea un camino dirigido a . Sea el número máximo tal que para cualquiera haya un arco de a . Después $norte$ $norte$ $norte$ $norte$ $T$ $n+1$ $v_{0}$ $T$ $v_{1},v_{2},\ldots,v_{n}$ $T\setminus \{v_{0}\}$ $i\in\{0,\ldots,n\}$ $j\leq yo$ $v_{j}$ $v_{0}$

v_{1},\ldots,v_{i},v_{0},v_{{i+1}},\ldots,v_{n}

es el camino orientado deseado. Esta prueba también proporciona un algoritmo para encontrar un camino hamiltoniano. Se conoce un algoritmo más eficiente que requiere la enumeración de todos los arcos [3] . $\O(n\log n)$

Esto significa que un torneo estrictamente conectado tiene un ciclo hamiltoniano [4] . Más estrictamente, cualquier torneo fuertemente conectado es pancíclico de vértice : para cualquier vértice v y para cualquier k de tres al número de vértices en el torneo, hay un ciclo de longitud k que contiene v [5] . Además, si el torneo es 4-conectado, cualquier par de vértices puede estar conectado por un camino hamiltoniano [6] .

Transitividad

Un torneo en el que y se denomina transitivo . En un torneo transitivo, los vértices se pueden ordenar completamente en orden de accesibilidad . $((a \ flecha derecha b)$ $(b\flecha derecha c))$ $\Flecha correcta$ $(a \ flecha derecha c)$

Condiciones equivalentes

Las siguientes declaraciones para un torneo con n vértices son equivalentes:

T es transitiva.
T es acíclico .
T no contiene ciclos de longitud 3.
La secuencia del número de victorias (el conjunto de resultados a medias) T es {0,1,2,…, n − 1}.
T contiene exactamente un camino hamiltoniano.

Teoría de Ramsey

Los torneos transitivos juegan un papel esencial en la teoría de Ramsey , similar al papel que juegan las camarillas en los grafos no dirigidos. En particular, cualquier torneo con n vértices contiene un subtorneo transitivo con vértices [7] . La prueba es simple: elija cualquier vértice v como parte de este subtorneo y construya el subtorneo recursivamente en el conjunto de vecinos entrantes de v o en el conjunto de vecinos salientes, el que sea mayor. Por ejemplo, cualquier torneo con siete vértices contiene un torneo transitivo con tres vértices. El torneo de los siete mejores de Paley muestra que este es el máximo que se puede garantizar [7] . Sin embargo, Reid y Parker [8] demostraron que este límite no es estricto para algunos valores grandes de n . $1+\lpiso \log _{2}n\rpiso$

Erdős y Moser [7] probaron que hay torneos de n -vértices sin subtorneos transitivos de tamaño . Su prueba usa contar : el número de formas en que un torneo transitivo con k vértices puede estar contenido en un torneo más grande con n vértices etiquetados es $2+2\lpiso \log _{2}n\rpiso$

{\binom {n}{k}}k!2^{{{\binom {n}{2}}-{\binom {k}{2}}}},

y para k mayor que este número, es demasiado pequeño para que haya un torneo transitivo en cada uno de los diferentes torneos del mismo conjunto de n vértices etiquetados. $2+2\lpiso \log _{2}n\rpiso$ $2^{{{\ binom {n}{2))))$

Torneos Paradox

El jugador que gane todos los juegos será naturalmente 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 todos los jugadores pierden al menos un juego se llama torneo 1-paradójico. De manera más general , se dice que un torneo T = ( V , E ) es k -paradójico si para cualquier subconjunto S de elementos k del conjunto V existe un vértice v 0 en tal que para todos . Usando el método probabilístico , Erdős demostró que para cualquier k fijo bajo la condición | v | ≥ k 2 2 k ln(2 + o(1)) casi cualquier torneo en V es k -paradójico [9] . Por otro lado, un argumento simple muestra que cualquier torneo k -paradójico debe tener al menos 2 k +1 − 1 jugadores, lo que ha sido mejorado a ( k + 2)2 k −1 − 1 por Esther y György Sekeresami (1965) ) [ 10] . Hay un método explícito para construir k -torneos paradójicos con k 2 4 k −1 (1 + o(1)) jugadores desarrollado por Graham y Spencer, a saber, el torneo Paley [11] . $V\setminus S$ $v_{0}\flecha derecha v$ $v\en S$

Condensación

La condensación de cualquier torneo es un torneo transitivo. Por lo tanto, incluso si el torneo no es transitivo, los componentes fuertemente conectados del torneo pueden ordenarse por completo [12] .

Secuencias de resultados y conjuntos de resultados

La secuencia de resultados del torneo es una secuencia no decreciente de semigrados de resultados de los vértices del torneo. El conjunto de resultados del torneo es el conjunto de enteros que son semigrados de resultado de los vértices del torneo.

Teorema de Landau (1953) - Una secuencia no decreciente de enteros es una secuencia de resultados si y solo si: $(s_{1},s_{2},\cdots,s_{n})$

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \elegir 2},$ por $i=1,2,\cdots,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \elegir 2}.$

Sea el número de secuencias distintas de resultados de tamaño . La secuencia comienza con: $s(n)$ $norte$ $s(n)$

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

(secuencia A000571 en OEIS )

Winston y Kleitman probaron que para n suficientemente grande

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

donde Takacs mostró más tarde [13] usando alguna conjetura plausible pero no probada de que $c_{1}=0,049.$

s(n)<c_{2}4^{n}n^{{-{5 \over 2}}},

dónde $c_{2}<4,858.$

Juntos, esto indica que

s(n)\en \Theta (4^{n}n^{{-{5 \over 2}}}).

Aquí se refleja el límite asintóticamente estricto . $\Theta$

Yao demostró [14] que cualquier conjunto no vacío de enteros no negativos es el conjunto de resultados de algún torneo.

Véase también

Notas

↑ HG Landau. Sobre las relaciones de dominación y la estructura de las sociedades animales. tercero La condición para una estructura de puntuación // Boletín de Biofísica Matemática. - 1953. - T. 15 , núm. 2 . - S. 143-148 . -doi : 10.1007/ BF02476378 .
↑ Lazló Redei. Ein kombinatorischer Satz // Acta Litteraria Szeged. - 1934. - T. 7 . - S. 39-43 .
↑ A. Bar-Noy, J. Naor. Clasificación, conjuntos de retroalimentación mínimos y rutas de Hamilton en torneos // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , nº. 1 . - S. 7-20 . -doi : 10.1137/ 0403002 .
↑ Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. - 1959. - T. 249 . - S. 2151-2152 .
↑ JW Luna. Sobre subtorneos de un torneo // Canadian Mathematical Bulletin. - 1966. - T. 9 , núm. 3 . - S. 297-301 . -doi : 10.4153 / CMB-1966-038-7 . Archivado desde el original el 3 de marzo de 2016.
↑ Carsten Thomassen. Torneos conectados por hamiltoniano // Journal of Combinatorial Theory, Serie B. - 1980. - V. 28 , no. 2 . - S. 142-163 . - doi : 10.1016/0095-8956(80)90061-1 .
↑ 1 2 3 Paul Erdős, Leo Moser. Sobre la representación de grafos dirigidos como uniones de órdenes // Magyar Tud. Akád. Estera. Int. de Kutato Kozl. - 1964. - T. 9 . - S. 125-132 . Archivado desde el original el 13 de diciembre de 2013.
↑ K. B. Reid, E. T. Parker. Refutación de una conjetura de Erdös y Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , núm. 3 . - S. 225-238 . - doi : 10.1016/S0021-9800(70)80061-8 .
↑ Paul Erdős. Sobre un problema de teoría de grafos // The Mathematical Gazette. - 1963. - T. 47 . - S. 220-223 . — . Archivado desde el original el 22 de diciembre de 2014.
↑ Esther Szekeres, George Szekeres. Sobre un problema de Schütte y Erdős // The Mathematical Gazette. - 1965. - T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. Una solución constructiva a un problema de torneo // Canadian Mathematical Bulletin. Boletín canadiense de matemáticas. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. La teoría de los torneos de todos contra todos // American Mathematical Monthly. - 1966. - T. 73 , núm. 3 . - S. 231-246 . -doi : 10.2307/ 2315334 . — .
↑ Lajos Takacs. Una excursión de Bernoulli y sus diversas aplicaciones // Avances en la probabilidad aplicada. - 1991. - T. 23 , núm. 3 . - S. 557-585 . -doi : 10.2307/ 1427622 . . _
↑ TX Yao. Sobre la conjetura de Reid de conjuntos de puntuación para torneos // Ciencia china. Toro. - 1989. - T. 34 . - S. 804-808 .