¿Cuál es el número mínimo de evita para nunca tener una coincidencia en Dota 2?

Question

En Dota2, los jugadores pueden evitar a otros jugadores para que nunca vuelvan a estar en el mismo equipo nuevamente.

Cada partida es de cinco jugadores contra cinco jugadores y debe haber un total de 10 jugadores.

Supongamos que todos los jugadores son jugadores solitarios y que todos tienen el mismo nivel de habilidad.

Cuando un jugador busca una partida, el jugador será colocado aleatoriamente en una partida con otros cuatro jugadores en su equipo y cinco jugadores en el otro equipo.

Deje que el número de jugadores sea $N$; es un múltiplo de 10.

Cualquier jugador puede evitar a cualquier jugador que deseen, pero no a ellos mismos.

Si todos los jugadores buscan una partida al mismo tiempo, ¿cuál es el número mínimo de evita en total que es necesario para que todos esos jugadores nunca encuentren una partida?

Answer 1

Esto puede traducirse en un problema en teoría de grafos extremal. Específicamente, considera el grafo $G$ en $N$ vértices dados por los jugadores donde hay una arista entre dos vértices si ningún jugador tiene al otro evitado. Para que cualquier jugador pueda encontrar un partido, deben existir dos conjuntos disjuntos de $5$ vértices tal que en cada conjunto todos los vértices tienen una arista entre ellos; el término en teoría de grafos para estos conjuntos es cliques. Por lo tanto, la pregunta es:

¿Cuál es el mayor número de aristas que puede tener $G$ sin contener dos cliques disjuntos de tamaño $5$?

Este es un caso especial del problema de subgrafo prohibido, donde el subgrafo prohibido es $H = K_5 \sqcup K_5$. La respuesta es clásica si en lugar de evitar $K_5$ se pregunta sobre el teorema de Turán: el grafo que maximiza el número de aristas es un grafo de Turán $T(N, 4)$, y asumiendo para simplicidad que $4 \mid N$ tiene

$$\frac{3N^2}{8}$$

aristas. La construcción del grafo de Turán tiene una interpretación curiosa en este caso: se divide el conjunto de jugadores en $4$ subconjuntos disjuntos del mismo tamaño $\frac{N}{4}$, que podríamos llamar "anticlanes". Los miembros de un anticlán se odian mutuamente, por lo que se evitan, pero se llevan bien con los demás. Por lo tanto, no son posibles equipos de $5$ jugadores porque en cualquier grupo de $5$ jugadores hay al menos dos en el mismo anticlán. No es difícil ver que esta construcción produce ${4 \choose 2} \left( \frac{N}{4} \right)^2$ aristas, lo que da el recuento anterior.

Este es un límite inferior sobre el número deseado de aristas; claramente podemos hacer al menos un poco mejor agregando, por ejemplo, una sola arista adicional. Un resultado más general sobre el problema de subgrafo prohibido es el teorema de Erdős–Stone, que da un límite asintótico para el problema de subgrafo prohibido para un grafo $H$ en términos del número cromático de $H$. El número cromático de $K_5 \sqcup K_5$ es el mismo que para $K_5$, es decir, $5$, y por lo tanto, el teorema establece que el número máximo de aristas es asintóticamente

$$\left( \frac{3}{8} + o(1) \right) N^2$$.

Entonces es posible hacer un poco mejor que la construcción del "anticlán" pero no mucho mejor. Sería bueno obtener un número más específico aquí.

Para mejorar el grafo de Turán, un vértice puede conectarse con cada otro vértice; en términos de jugadores, un jugador puede decidir que está bien con su anticlán después de todo. Esto permite muchos equipos de $5$ jugadores pero todos contienen a este jugador único, por lo que aún no podemos tener dos equipos, y esto agrega $\frac{N}{4} - 1$ aristas. Agregar una sola arista adicional produce un segundo equipo (al menos si $N$ es lo suficientemente grande), por lo que no es posible agregar más aristas. Supongo que esta construcción es óptima, así que conjecturo que si $4 \mid N$ y $N \ge 16$ aproximadamente, el número máximo exacto de aristas es

$$\frac{3N^2}{8} + \frac{N}{4} - 1.$$

Este es el complemento del número de evitaciones, por lo que para obtener el número de evitaciones necesitamos ${N \choose 2}$ menos este número, que es (conjeturalmente, y con las condiciones anteriores sobre $N$)

$$\boxed{ \frac{N^2}{8} - \frac{3N}{4} + 1}.$$

Tenemos una construcción que muestra que este número funciona, pero puede ser posible que el verdadero mínimo sea más pequeño.

Answer 2

Teorema de Turán. Si un grafo $G$ es libre de $K_{r+1}$, entonces $e(G)\le \frac{r-1}{r}\frac{|G|^2}{2}$, y el único grafo posible con $\frac{r-1}{r}\frac{|G|^2}{2}$ aristas es el grafo de Turán $r$-partito.

Respondamos la conjetura de Yuan de manera positiva para $n\ge 144$:

Proposición. Si un grafo $G$ con $n\ge 144$ vértices tiene $\ge \frac{3n^2}{8}+\frac{n}{4}$ aristas, entonces $G$ contiene dos $K_5$ disjuntos, denotado por $2K_5$.

prueba. Supongamos que $G$ es un grafo con $n$ vértices con $\ge \frac{3n^2}{8}+\frac{n}{4}$ aristas y no contiene $2K_5$.

Consideremos el número de cliques $w(G)($ que seguramente es $\le 9)$ de $G$.

El caso $w(G)\le 4$ se deduce fácilmente por el teorema de Turán en $K_4$.

Caso 1. $w(G)=5$. Sea $K$ induce una clique de $5$ en $G$, entonces $G-K$ es libre de $K_5$, y cada $v\in G-K$ puede tener $\le 4$ vecinos dentro de $K$. Así que $$e(G)\le \binom{5}{2}+\frac{3}{4}\frac{(n-5)^2}{2}+(n-5)4<\frac{3n^2}{8}+\frac{n}{4}.$$

Caso 2. $w(G)=9$. Sea $K$ induce una clique de $9$ en $G$, entonces $G-K$ es libre de $K_5$, y cada $v\in G-K$ puede tener $\le 3$ vecinos dentro de $K$, de lo contrario habrá un $2K_5$. Así que $$e(G)\le \binom{9}{2}+\frac{3}{4}\frac{(n-9)^2}{2}+(n-9)3<\frac{3n^2}{8}+\frac{n}{4}.$$

La prueba de los casos restantes $w(G)=6,7,8$ es similar. Solo presentamos el caso $w(G)=6$ aquí, que es el caso más difícil y donde la cota inferior $n\ge 144$ proviene. Necesitamos encontrar un conjunto de $9=10-1$ vértices para calcular el número de aristas. El número $6$ es el más lejano de $9$, y agregaremos un triángulo adecuado a la $6$-clique para formar el conjunto de $9$ vértices. (Para otros casos, agregaremos una $2$-clique (una arista) a la $7$-clique y un vértice a la $8$-clique).

Si tienes problemas al tratar los casos $7,8,9$, por favor házmelo saber en el área de comentarios y completaré la prueba entera.

Caso 3. $w(G)=6$. Sea $K=\{1,2,3,4,5,6\}$ induce una clique de $6$ en $G$, entonces $$e(K_6,G-K_6)\ge \frac{3n^2}{8}+\frac{n}{4}-\binom{6}{2}-\frac{3}{4}\frac{(n-6)^2}{2}$$ $$=\frac{19}{4}n-C, \text{ donde $C=\frac{57}{2}$.}$$

Sea $X\subseteq V(G-K)$ denote los vértices que tienen grado exactamente $5$ en $K$. Entonces $$\frac{19}{4}n-C\le 5|X|+4(n-6-|X|),$$ entonces $|X|\ge \frac{3}{4}n-C_1$, donde $C_1=\frac{9}{2}$.

Afirmación. El subgrafo inducido $G[X]$ contiene un triángulo.

Supongamos que no, entonces $$e(G)\le e(X)+e(X,V(G)-X)+e(V(G)-X)$$ $$\le \frac{1}{4}\left(\frac{3}{4}n-C_1\right)^2+\left(\frac{3}{4}n-C_1\right)\left(\frac{1}{4}n+C_1\right)+\frac{3}{8}\left(\frac{1}{4}n+C_1\right)^2$$ $$= \frac{45}{128}n^2+C_2n+C_3, \text{ donde } C_2=\frac{13}{16}C_1=\frac{117}{32}, C_3=-\frac{3}{8}C_1^2=-\frac{243}{32}$$$$ < \frac{3}{8}n^2 +\frac{1}{4}n, \text{ cuando } n\ge 144.$$ Entonces $G[X]$ debe contener un triángulo, denotado por $abca$.

Ahora consideremos $G[K\cup \{a,b,c\}]=G[A]$, supongamos que $1,2,3\in K$ son vecinos comunes de $\{a,b,c\}$, entonces $G[\{1,2,3\},\{4,5,6\}]$ y $G[\{1,2,3\},\{a,b,c\}]$ son dos $6$-cliques. Por lo tanto, cualquier vértice en $G-A$ tiene $\le 7$ vecinos en $A$ (si $N(v)=\{2,3,4,5,6,a,b,c\}$, entonces $\{v,2,a,b,c\}$, $\{1,3,4,5,6\}$ son $2K_5$; si $N(v)=\{1,2,3,4,5,a,b,c\}$, entonces $\{2,3,4,5,6\}$, $\{1,v,a,b,c\}$ son $2K_5$).

Además, si $G-A$ es el grafo de Turán con $4$ partes, entonces hay al menos un vértice con $\le 6$ vecinos en $A$, de lo contrario habrá un $2K_5$. (Si $|N_A(v)|\ge 7$ para todos salvo uno o dos vértices en $V(G)-A$, entonces hay un vértice $x$ en $A$ con grado $\ge \frac{7(n-10)}{9}$ en $G-A$, y $\frac{7(n-10)}{9}\ge \lceil\frac{3}{4}(n-9)\rceil$, $x$ se encuentra en una clique de $5$ cuya intersección con $A$ es exactamente $x$). Entonces, $$e(G)\le 7(n-9)+\frac{3}{8}(n-9)^2-1+\binom{9}{2}-3=\frac{3}{8}n^2+\frac{1}{4}n-\frac{5}{8}$$$$<\frac{3}{8}n^2+\frac{1}{4}n.$$