3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Mar 2 '20 at 8:45
  • $\begingroup$ I get $p(16)$ to be about $0.64$. Why are you sure $p(n)\to1$? $\endgroup$ – Gerry Myerson Mar 2 '20 at 8:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Mar 2 '20 at 10:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Mar 2 '20 at 11:41
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.