Torneo (teoría de grafos)

En teoría de grafos, un torneo es un grafo dirigido cuyos vértices representan un conjunto de actores o competidores en alguna competición o acontecimiento, y cuyas aristas representan el triunfo de un competidor sobre otro. Un caso particular interesante es el de los «torneos de comparación apareada equilibrada» o round-robin, donde cada actor compite contra los demás una única vez, en un sistema de todos contra todos. En este último caso, el grafo coincide con lo que se obtendría asignándole una dirección a cada arista de un grafo completo no dirigido, de modo que cada par de vértices está conectado exactamente por una arista.​

Muchas de la propiedades importantes de los torneos fueron investigadas primeramente por Landau con el propósito de modelar relaciones de dominancia en grupos de gallinas.​ Las actuales aplicaciones de los torneos incluyen el estudio de la teoría de votación y la teoría de la selección social, entre otras cosas. El nombre de torneo se originó de la interpretación de un grafo como resultado de un sistema de todos contra todos en el cual cada jugador juega exactamente con cada uno de los demás una única vez, y en el cual no existen tablas. En el digrafo torneo, los vértices corresponden a los jugadores. Los arcos entre cada par de jugadores están orientados de ganador a perdedor. Si un jugador $a$ vence al jugador $b$, entonces se dice que $a$ domina a $b$.

Este tipo de grafos está relacionado con el modelo de Bradley–Terry, método estadístico de comparaciones entre pares, utilizado para estimar las tendencias de una población a la dominación.​

Caminos y Ciclos

Cualquier torneo con un número finito de vértices contiene un camino hamiltoniano, es decir, un camino dirigido con todos los $n$ vértices.​ Esto es fácilmente demostrado por inducción en $n$: supongamos que el enunciado se cumple para $n$, y considere cualquier torneo $T$ de $n+1$ vértices. Seleccionemos un vértice $v_{0}$ de $T$ y consideremos un camino dirigido $v_{1},v_{2},\ldots ,v_{n}$ en $T\setminus \{v_{0}\}$. Ahora sea $i\in \{0,\ldots ,n\}$ máximo tal que para todo $j\leq i$ exista un arco desde $v_{j}$ a $v_{0}$.

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

es un camino dirigido como se quería. Este argumento también provee una forma de encontrar un camino hamiltoniano. Algoritmos más eficientes, que requieren examinar solo $\ O(n\log n)$ de los arcos, son conocidos.​

Esto implica que un torneo fuertemente conexo tiene un ciclo hamiltoniano.​ Un resultado más fuerte es que todo torneo fuertemente conexo es vértice pancíclico: para todo vértice v, y todo k en el rango desde tres hasta la cantidad de vértices del torneo, existe un ciclo de longitud k que contiene a v.​ Sin embargo, si un torneo es 4-conexo, cada par de vértices puede ser conectado con un camino hamiltoniano.​

Transitividad

Un torneo en el cual $((a\rightarrow b)$ y $(b\rightarrow c))$ $\Rightarrow$ $(a\rightarrow c)$ es llamado transitivo. En un torneo transitivo, los vértices pueden ser totalmente ordenado por alzanzabilidad.

Condiciones equivalentes

Las siguientes condiciones son equivalentes para un torneo T de n vértices:

1. T es transitivo.
2. T es un acíclico.
3. T no contiene un ciclo de longitud 3.
4. La secuencia de grados de salida de T es {0,1,2,...,n − 1}.
5. T tiene exactamente un camino hamiltoniano.

Teoría de Ramsey

Los torneos transitivos juegan un rol en la teoría de Ramsey análogo a los cliques en los grafos no diridos. En particular, cada torneo de n vértices contiene un subtorneo transitivo de $1+\lfloor \log _{2}n\rfloor$ vértices.​ La demostración es simple: seleccionemos un vértice v para que sea parte de este subtorneo, y formemos el resto del subtorneo recursivamente en el conjunto de vecinos entrantes de v o en el conjunto de los vecinos salientes de v, cual sea el más grande. Por ejemplo, todo torneo de siete vértices contiene un subtorneo transitivo de tres vértices; el torneo Paley de siete vértices muestra que esto es lo mejor que se puede garantizar.​ Sin embargo, demostró que este límite no es justo para algunos valores mayores de  n.​

Existen torneos de n vértices sin un subtorneo transitivo de tamaño $2+2\lfloor \log _{2}n\rfloor$.​ La demostración utiliza un argumentos combinatorios: la cantidad de formas de que un torneo trnasitivo de k elementos pueda ocurrir como subtorneo de un torneo mayor de n vértices enumerados es

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

y cuando k es mayor que $2+2\lfloor \log _{2}n\rfloor$, este valor es demasiado pequeño para permitir la acurrencia de un torneo transitivo dentro de cada uno de los $2^{\binom {n}{2}}$ torneos diferentes en el mismo conjunto de n vértices enumerados.

Torneos paradójicos

Un jugador que gane todos los juegos es naturalmente el ganador del torneo. Sin embargo la existencia de torneos no transitivos muestra que puede que no exista tal jugador. Un torneo para el cual todo jugador pierde al menos un juego es llamado un torneo 1-paradójico. Generalizando, un torneo T=(V,E) es llamado k-paradójico si para todo subconjunto de k elementos S de V existe un vértice v₀ en $V\setminus S$ tal que $v_{0}\rightarrow v$ para todo $v\in S$. Mediante el método probabilístico, Paul Erdős demostró que para un valor fijo de k, si |V| ≥ k²2^kln(2 + o(1)), entonces casi todo torneo en V es k-paradójico.​ Por otro lado, un fácil argumento muestra que para cualquier torneo k-paradójico debe tener el menos 2^k+1 − 1 jugador, el cual puede ser mejorado a (k + 2)2^k−1 − 1.​ Existe una construcción explícita de torneos k-paradójicos con k²4^k−1(1 + o(1)) jugadores llamado torneo Paley.​

Condensación

La condensación de cualquier torneo es un torneo transitivo. Por lo tanto, incluso para torneos que no son transitivos, sus componentes fuertemente conexos pueden ser ordenados totalmente.​

Secuencia de grados y conjuntos de grados

La secuencia de grados de un torneo es la secuencia no decreciente de grados de salida de sus vértices. El conjunto de grados de un torneo es el conjunto de enteros que son los grados de salida de sus vértices.

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

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

Sea $s(n)$ la cantidad de secuencias de grado diferentes de tamaño $n$. Los primeros términos de la secuencia $s(n)$ (sucesión A000571 en OEIS):

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

Winston y Kleitman demostraron que para un n suficientemente grande:

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

donde $c_{1}=0.049.$ Posteriormente se demostró que, utilizando algunas asunciones razonables, pero no demostradas, que

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

donde $c_{2}<4.858.$​

Juntas, estas ecuaciones muestran evidencia de que:

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

Aquí $\Theta$ significa una cota superior asintótica.

Yao demostró que todo conjunto de enteros no negativos es la secuencia de grados de algún torneo.​

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

• Datos: Q1320634