Piedra, papel o tijera...

Question

Un grafo dirigido cuyo grafo no dirigido subyacente es completo se denomina grafo torneo . Llamemos a un grafo dirigido (finito) equilibrado si cada vértice tiene tantas aristas entrantes como salientes. La pregunta es: ¿se han clasificado los torneos equilibrados? (La forma más débil de "clasificar" podría ser: dado $n$ determinar el número de torneos equilibrados en $n$ vértices hasta el isomorfismo).

He aquí algunas observaciones elementales:

• para incluso $n$ no hay un torneo equilibrado en $n$ vértices.

• para impar $n$ hay un torneo equilibrado estándar en $n$ vértices: toma como conjunto de vértices $\{0,\ldots,n-1\}$ e incluir una flecha de $i$ a $i+j \mod n$ para $1 \le j \le (n-1)/2$ . (El grupo de automorfismo es cíclico de orden $n$ .)

• para $n=1$ , $n=3$ y $n=5$ el único torneo equilibrado es el estándar.

• para $n=7$ existe un torneo equilibrado no estándar: para construirlo invierta un $3$ -en el b.t. estándar, para ver que no es estándar mira el "out-link" de un vértice apropiado. (El grupo de automorfismo es trivial).

• Se puede tomar una especie de producto corona para construir ejemplos cuyos grupos de automorfismo sean abelianos, no cíclicos. Hay otras construcciones para producir ejemplos.

La motivación de esta pregunta es simplemente la siguiente: el b.t. en $3$ vértices codifica el juego piedra-papel-tijera. El de $5$ vértices codifica el juego piedra-papel-tijera-lagarto-Spock (si no lo conoces, puedes averiguarlo una vez sepas que "lagarto envenena a Spock" [editar, gracias a Ramiro de la Vega:] y que "papel refuta a Spock"). En $7$ si hay alguna opción, ¿cuánta y cuál?

Además: ¿alguien conoce la expresión adecuada para "equilibrado"? [editar: según David Speyer el término en este contexto es "torneo regular"].

Answer 1

Su secuencia es Sloane A096368 . Sloane enlaza con esta página que contiene los archivos de todos los ejemplos hasta $13$ vértices. MathSciNet tiene 30 artículos con "torneo regular" en el título, ninguno de los cuales parece saber mucho sobre la enumeración hasta el isomorfismo. Un vistazo rápido a los artículos con "torneo equilibrado" en el título sugiere que ese término significa otra cosa, así que yo buscaría "torneo regular".

McKay demuestra una fórmula asintótica para el número de torneos regulares ETIQUETADOS de la forma $2^{\binom{n}{2}} e^{-O(n \log n)}$ . (Véase su artículo para una afirmación mucho más precisa.) Dado que el tamaño de $n!$ es "sólo" $e^{O(n \log n)}$ podemos deducir que el número de clases de isomorfismo también es $2^{\binom{n}{2}} e^{-O(n \log n)}$ y, en particular, a $\infty$ como $n \to \infty$ .

---

Puedo decir algo más sobre el problema etiquetado, en el que no cotizamos por automorfismo. Este es Sloane A007079 .

El número que queremos es el coeficiente de $\prod_{i=1}^{n} x_i^{(n-1)/2}$ en $\prod_{1 \leq i < j \leq n} (x_i+x_j)$ cada factor corresponde a una arista y elegir $x_i$ o $x_j$ corresponde a la orientación de esta arista. Este polinomio es el Polinomio de Schur $s_{(n-1)(n-2)\cdots 321}(x_1, \ldots, x_n)$ ; esto se deduce de la fórmula de la proporción de alternantes. Por lo tanto, se busca el Número de Kotska $$K_{(n-1)(n-2)\cdots 321,\ mmm \cdots m} \ \mbox{where} \ m=(n-1)/2.$$

No creo que exista una fórmula cerrada para este número de Kotska.

---

Aquí hay algo interesante que no pude hacer funcionar, pero que tal vez ayude a alguien más. Esencialmente por definición, este número de Kostka es la dimensión del espacio de invariantes diagonales en la representación de $SL_n$ asociada a la partición $(n-1, n-2, \cdots, 2,1)$ . Y este espacio vectorial viene con un $S_n$ -a partir de la incrustación de $S_n$ en $SL_n$ .

Por desgracia, ¡no coinciden! Cuando $n=3$ hay dos torneos etiquetados. (Orientar el triángulo en el sentido de las agujas del reloj o en sentido contrario.) Entonces una permutación $\sigma$ en $S_3$ conserva o cambia los torneos en función del signo de $\sigma$ . La correspondiente representación de permutación de $S_3$ es la suma directa de la trivial y la rep. signo. Por el contrario, la representación de $S_3$ en las invariantes diagonales de $V_{21}$ es el $2$ -irrep de $S_3$ .

Aun así, sería genial si pudiéramos encontrar una relación más profunda entre estas dos representaciones de $S_n$ que el simple hecho de que tengan la misma dimensión. En particular, recuerde que el número de órbitas en una representación de permutación es siempre la multiplicidad de la rep trivial, por lo que uno podría imaginar contando clases de isomorfismo por teoría de la representación si podemos encontrar una buena descripción alternativa de la representación del torneo.