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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

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