# Difference between two largest degrees

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 $$S$$ be the set of all out-degrees. Let $$s_1$$ be the largest element of $$S$$, and $$s_2$$ the next largest. (If $$S$$ is a singleton, let $$s_2=s_1$$.)

Let $$c\in (0,1)$$ be a constant. What is $$\lim_{n\rightarrow\infty}\text{Pr}[s_1-s_2?

My guess is that the limit should go to $$1$$, that is, the two largest out-degrees are close to each other compared to the size of the tournament.

• It might be worth parenthesizing the second sentence, or otherwise marking it to indicate that it's just defining what you say in the first sentence; it took me a moment to realize that you weren't starting from a tournament graph and then drawing additional edges... – Steven Stadnicki Feb 26 '20 at 20:40

## 2 Answers

You guess is correct, assuming that by $$x_1$$ and $$x_2$$ you meant $$s_1$$ and $$s_2$$.

Indeed, the probability in question is $$1-p_n$$, where $$\begin{equation} p_n:=P(\exists i\in[n]\ D_i-\max_{j\in[n]\setminus\{i\}}D_j\ge cn), \end{equation}$$ where $$[n]:=\{1,\dots,n\}$$ and $$D_i$$ is the out-degree of the $$i$$th vertex. We can write $$\begin{equation} D_i=\sum_{j\in[n]}D_{ij}, \end{equation}$$ where $$\begin{equation} D_{ij}:=I\{X_{ij}=1\}, \end{equation}$$ $$I\{\cdot\}$$ is the indicator function, and $$(X_{ij})$$ is a random $$n\times n$$ skew-symmetric matrix whose above-diagonal entries are independent Rademacher random variables (r.v.'s), with $$P(X_{ij}=\pm1)=1/2$$ if $$1\le i.

We need to show that $$p_n\to0$$ (as $$n\to\infty$$), for each $$c\in(0,1)$$. In fact, $$\begin{equation} p_n\le nP(D_1-\max_{j\in[n]\setminus\{1\}}D_j\ge cn) \le nP(D_1-D_2\ge cn). \end{equation}$$ Next, $$\begin{equation} D_1-D_2=D_{12}-D_{21}+\sum_{j=3}^n Y_j, \end{equation}$$ where $$Y_j:=D_{1j}-D_{2j}$$, so that the $$Y_j$$'s are iid zero-mean r.v.'s, with $$|Y_j|\le1$$. Also, $$D_{12}-D_{21}\le1$$. So, by (say) Hoeffding's inequality, for all large enough $$n$$, $$\begin{equation} p_n\le nP(D_1-D_2\ge cn)\le nP\Big(\sum_{j=3}^n Y_j\ge cn-1\Big)\le ne^{-(cn-1)^2/(2(n-2))}\to0, \end{equation}$$ as desired.

The outdegree of every fixed vertex is distributed binomialy with the mean $$n/2$$ and the variance $$n/4$$. Hence, the probability that the outdegree deviates from $$n/2$$ by $$cn/3$$ at least is extremely small, and by the union bound so is the probability that there is at least one vertex with the outdegree deviating from $$n/2$$ by $$cn/3$$. This means that with probability $$1-o(1)$$, the outdegrees of all vertices are in the range $$(n/2-cn/3,n/2+cn/3)$$, confirming your conjecture.

• @pi66 It means the two largest differ by at most $2cn/3$ with high probability. Actually all the outdegrees are the same within $n^{1/2}\log n$ with high probability, as can be shown by Iosef's method. – Brendan McKay Feb 27 '20 at 9:45