# Unique maximum degree in tournament

Consider a uniform random tournament with $$n$$ vertices. (Between any two vertices $$x,y$$, with probability $$0.5$$ draw an edge from $$x$$ to $$y$$; otherwise draw an edge from $$y$$ to $$x$$.) Let $$p(n)$$ denote the probability that there is only one vertex with the maximum out-degree. What is $$\lim_{n\rightarrow\infty}p(n)$$?

I would be surprised if this statement hasn't been written and proved anywhere, but I can't find it. Does anyone know of a reference, or a result that implies it?

• The number of tournaments with a unique winner is tabulated at oeis.org/A013976 – the total number of tournaments on $n$ vertices is $2^{n(n-1)/2}$, so you can do some calculations to see whether it looks like the probability is going to one. – Gerry Myerson Mar 2 '20 at 8:45
• I get $p(16)$ to be about $0.64$. Why are you sure $p(n)\to1$? – Gerry Myerson Mar 2 '20 at 8:54
• Not only the maximum outdegree but quite a few of the largest outdegrees are unique. This is known and I'm looking for a place it is written down. It can be proved by fairly elementary means. – Brendan McKay Mar 2 '20 at 10:49
• Hmmm, not in the places I looked. The proof is almost the same as proving that the maximum degree vertex of a random undirected graph is unique, in Bollobas' book "Random Graphs". Convergence is slow: for tournaments it passes 90% at around 900 vertices. – Brendan McKay Mar 2 '20 at 11:41

## 1 Answer

I can't find a published proof of this known result, but here is a close miss.

In this paper, page 256, is a short proof that a random undirected graph has a unique vertex of maximum degree almost surely. If you replace "graph" by "tournament" and "degree" by "out-degree", the exact same proof works for tournaments.

The reason this works is that the degree of a given vertex in a random graph, or out-degree in a random tournament, have the same binomial distribution Bin$$(n-1,\frac12)$$. Moreover, the degrees/out-degrees of different vertices are almost independent.