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?

Improve this question
$\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, 2020 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, 2020 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, 2020 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, 2020 at 11:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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