2
$\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 $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<cn]$?

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$ – Steven Stadnicki Feb 26 '20 at 20:40
4
$\begingroup$

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<j\le n$.

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$ – Brendan McKay Feb 27 '20 at 9:45

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.