25
$\begingroup$

In Dota2, players can avoid other players so that they will never be in the same team again.

Every match is five players against five players and must have 10 players in total.

Let's assume that all players are solo players and that they are all at the same level of skill.

When a player searches for a match, the player will randomly be placed in a match with four other players on their team and five players on the other team.

Let the number of players be $N$; it's a multiple of 10.

Any player can avoid any player they want, but not themselves.

If every player searches for a match at the same time, what's the minimum number of avoids in total that's necessary for all those players to never find a match?

$\endgroup$
1
  • 5
    $\begingroup$ This is a very fun graph theory problem. I wouldn't be surprised if it's an open problem. This seems very closely related to Ramsey numbers, which we only have pretty rough upper and lower bounds for. It's an active field of modern mathematics. $\endgroup$
    – jMdA
    Commented Jun 21 at 21:09

2 Answers 2

33
$\begingroup$

This can be translated into a problem in extremal graph theory. Namely, consider the graph $G$ on $N$ vertices given by the players where there is an edge between two vertices if neither player has the other one avoided. In order for any players to be able to find a match, there must be two disjoint sets of $5$ vertices such that in each set all of the vertices have an edge between them; the graph theory term for these sets is cliques. So the question is:

What is the largest number of edges that $G$ can have while not containing two disjoint cliques of size $5$?

This is a special case of the forbidden subgraph problem, where the forbidden subgraph is $H = K_5 \sqcup K_5$. The answer is classical if instead we ask to avoid $K_5$ and is given by Turán's theorem: the graph that maximizes the number of edges is a Turán graph $T(N, 4)$, and assuming for simplicity that $4 \mid N$ it has

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

edges. The construction of the Turán graph has a funny interpretation in this case: you partition the set of players into $4$ disjoint subsets of the same size $\frac{N}{4}$, which we might call "antiguilds" or "anticlans." The members of an anticlan hate each other, and so have each other avoided, but they're cool with everyone else. So no $5$-player teams are possible because in any group of $5$ players there are at least two in the same anticlan. It's not hard to see that this construction produces ${4 \choose 2} \left( \frac{N}{4} \right)^2$ edges, which gives the above count.

This is a lower bound on the desired number of edges; we can clearly do at least a little better by adding, for example, a single additional edge. A more general result on the forbidden subgraph problem is the Erdős–Stone theorem, which gives an asymptotic for the forbidden subgraph problem for a graph $H$ in terms of the chromatic number of $H$. The chromatic number of $K_5 \sqcup K_5$ is the same as for $K_5$, namely $5$, and so the theorem gives that the maximum number of edges is asymptotically

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

So it's possible to do a little better than the "anticlan" construction but not much better. It would be nice to get a more specific number here.

To improve on the Turán graph, one vertex can be connected to every other vertex; in player terms, one player can decide that he's cool with his anticlan after all. This allows many $5$-player teams but they all contain this single player so we still can't get two teams, and this adds $\frac{N}{4} - 1$ edges. Adding a single additional edge produces a second team (at least if $N$ is large enough) so it's not possible to add more edges. I'd guess that this construction is optimal, so I'll conjecture that if $4 \mid N$ and $N \ge 16$ or so the exact maximum number of edges is

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

This is the complement of the number of avoids, so to get the number of avoids we need ${N \choose 2}$ minus this number, which is (conjecturally, and with the above conditions on $N$)

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

We have a construction showing that this number works but it may be possible that the true minimum is smaller.

$\endgroup$
0
9
$\begingroup$

Turan theorem. If a graph $G$ is $K_{r+1}$-free, then $e(G)\le \frac{r-1}{r}\frac{|G|^2}{2}$, and the only possible graph with $\frac{r-1}{r}\frac{|G|^2}{2}$ edges is the $r$-partite Turan graph.

Let's answer Yuan's conjecture in positive for $n\ge 144$:

Proposition. If a graph $G$ on $n\ge 144$ vertices has $\ge \frac{3n^2}{8}+\frac{n}{4}$ edges, then $G$ contains two disjoint $K_5$, denoted by $2K_5$.

proof. Assume that $G$ is a graph on $n$ vertices with $\ge \frac{3n^2}{8}+\frac{n}{4}$ edges and contains no $2K_5$.

Consider the clique number $w(G)($ which is surely $\le 9)$ of $G$.

The case $w(G)\le 4$ is easily implied by turan theorem on $K_4$.

Case 1. $w(G)=5$. Let $K$ induces a $5$-clique in $G$, then $G-K$ is $K_5$-free, and every $v\in G-K$ can have $\le 4$ neighbors inside $K$. So $$e(G)\le \binom{5}{2}+\frac{3}{4}\frac{(n-5)^2}{2}+(n-5)4<\frac{3n^2}{8}+\frac{n}{4}.$$

Case 2. $w(G)=9$. Let $K$ induces a $9$-clique in $G$, then $G-K$ is $K_5$-free, and every $v\in G-K$ can have $\le 3$ neighbors inside $K$, otherwise there will be a $2K_5$. So $$e(G)\le \binom{9}{2}+\frac{3}{4}\frac{(n-9)^2}{2}+(n-9)3<\frac{3n^2}{8}+\frac{n}{4}.$$

The proof of the remaining cases $w(G)=6,7,8$ is similar. We only present the case $w(G)=6$ here, which is the hardest case and where the lower bound $n\ge 144$ comes form. We need to find a set of $9=10-1$ vertices in order to compute the number of edges. The number $6$ is farthest from $9$, and we will add a proper triangle to the $6$-clique to form the $9$-vertices set. (For other cases, We will add a $2$-clique (an edge) to $7$-clique and a vertex to $8$-clique).

If you meet troubles when dealing with the cases $7,8,9$, please let me know in the comment area and I will complete the whole proof.

Case 3. $w(G)=6$. Let $K=\{1,2,3,4,5,6\}$ induces a $6$-clique in $G$, then $$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{ where $C=\frac{57}{2}$.}$$

Let $X\subseteq V(G-K)$ denote the vertices that has degree exactly $5$ in $K$. Then $$\frac{19}{4}n-C\le 5|X|+4(n-6-|X|),$$ so $|X|\ge \frac{3}{4}n-C_1$, where $C_1=\frac{9}{2}$.

Claim. The induced subgraph $G[X]$ contains a triangle.

Suppose not, then $$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{ where } 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{ when } n\ge 144.$$ So $G[X]$ must contains a triangle, denoted by $abca$.

Now consider $G[K\cup \{a,b,c\}]=G[A]$, suppose $1,2,3\in K$ are common neighbors of $\{a,b,c\}$, then $G[\{1,2,3\},\{4,5,6\}]$ and $G[\{1,2,3\},\{a,b,c\}]$ are two $6$-cliques. Thus, any vertices in $G-A$ has $\le 7$ neighbors in $A$ (if $N(v)=\{2,3,4,5,6,a,b,c\}$, then $\{v,2,a,b,c\}$, $\{1,3,4,5,6\}$ are $2K_5$; if $N(v)=\{1,2,3,4,5,a,b,c\}$, then $\{2,3,4,5,6\}$, $\{1,v,a,b,c\}$ are $2K_5$).

In addition, if $G-A$ is the Turan graph with $4$ parts, then there are at least one vertices with $\le 6$ neighbors in $A$, otherwise there will be $2K_5.$ (If $|N_A(v)|\ge 7$ for all but at most one vertices in $V(G)-A$, then there is a vertex $x$ in $A$ with degree $\ge \frac{7(n-10)}{9}$ in $G-A$, and $\frac{7(n-10)}{9}\ge \lceil\frac{3}{4}(n-9)\rceil$, $x$ lies in a $5$-clique whos intersection with $A$ is exactly $x$). So, $$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.$$

$\endgroup$
3
  • 1
    $\begingroup$ Ah, removing the largest clique is a very natural idea, that's nice. Why do you need such a large lower bound on $n$? $\endgroup$ Commented Jun 22 at 18:59
  • 2
    $\begingroup$ @Qiaochu Yuan In the proof of the Claim, we make $n$ large such that $\frac{45}{128}n^2+C_2n+C_3<\frac{3}{8}n^2+\frac{1}{4}n$, where $C_2$ and $C_3$ depend on $C_1$, which requires a long computation. $\endgroup$ Commented Jun 22 at 19:38
  • 3
    $\begingroup$ @Qiaochu Yuan I reduced the large bound to $n\ge 144$ now. $\endgroup$ Commented Jun 23 at 6:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .