# Size of minimum cut in random graph

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$$.) The score of each vertex $$x$$ is the minimum number of edges that need to be deleted so that $$x$$ cannot reach some other vertex $$y$$. (So if $$x$$ already cannot reach some $$y$$, its score is $$0$$.)

Let $$p(n)$$ be the probability that the two highest scores are different. What is $$\lim_{n\rightarrow\infty}p(n)$$?

It is likely that all scores are positive (i.e. the graph is strongly connected), but I believe the two highest scores should be different (so the limit goes to $$1$$).

Yes, the limit goes to $$1$$.

An observation: by the Chernoff bound, with (very) high probability all vertices have degree between $$0.49n$$ and $$0.51n$$, so let's assume this holds in the following.

First, let's see that the number of edges needed to remove all directed paths from a given $$x$$ to a given $$y$$ is either the out-degree of $$x$$ or the in-degree of $$y$$, whichever is smaller.

To see this, suppose a smaller set $$S$$ of edges is removed. First, suppose $$S$$ leaves at least $$\tfrac{n}{10}$$ out-going edges from $$x$$ and at least $$\tfrac{n}{10}$$ edges going in to $$y$$. Pick $$\tfrac{n}{20}$$ out-neighbours of $$x$$ and a disjoint set of $$\tfrac{n}{20}$$ in-neighbours of $$y$$, and by the Chernoff bound with (very very) high probability there are more than $$\tfrac{1}{1000}n^2$$ edges from the first set to the second set in the tournament. These would have to all be in $$S$$, a contradiction.

We conclude that a linear sized set $$S$$ separating $$x$$ from $$y$$ has to contain all but at most $$\tfrac{n}{10}$$ edges either leaving $$x$$ or going into $$y$$. It can't be both, because then $$S$$ would have to be too big. Suppose it is the first; since $$S$$ is smaller than the out-neighbourhood of $$x$$, there is an out-neighbour $$z$$ of $$x$$ such that $$(x,z)$$ is not in $$S$$. Now $$S$$ can't contain many out-neighbours of $$z$$ (because it is small) so by the argument above there is a directed path from $$z$$ to $$y$$, so $$S$$ doesn't separate $$x$$ and $$y$$, a contradiction. The other case is symmetric.

OK, now the score of $$x$$ is whichever is smaller out of the out-degree of $$x$$ and the minimum in-degree of all $$y\neq x$$. Let $$z$$ be a vertex with minimum in-degree; then all $$x\neq z$$ have score at most the in-degree of $$z$$ (some may have smaller score; in fact there can only be very few such) and this score is slightly less than $$\tfrac{n}{2}$$. What is the score of $$z$$? This cannot be the outdegree of $$z$$, which is slightly bigger than $$\tfrac{n}{2}$$. So it's the in-degree of the vertex $$z'$$ of the tournament which has smallest in-degree and is not $$z$$.

That means that $$z$$ is a vertex with maximum score; it is the unique vertex with maximum score if it is the unique vertex with minimum in-degree, and otherwise it has the same score as most vertices in the graph (so in this case there are many vertices with maximum score).

In fact, the likely event is that $$z$$ is the unique vertex with maximum score. To see vaguely why this should be true, observe that the probability a given vertex has in-degree $$t$$ is $$2^{1-n}\binom{n}{t}$$, and the probability its in-degree is at most $$t$$ is $$2^{1-n}\sum_{i\le t}\binom{n}{i}$$. The in-degree of different vertices is close to independent, and so we expect the minimum to be around $$\tfrac{n}{2}-\tilde{O}(\sqrt{n})$$ (by calculation). For $$t$$ in this range, the probability of a given vertex having in-degree $$t$$ is something like $$n^{-3/2}$$, so the probability that two given vertices have degrees $$t$$ and $$t'$$ in this range is something like $$n^{-3}$$ (assuming, which is cheating, independence). That means that the expected number of pairs of vertices with degree $$t$$ and $$t'$$ is something like $$n^{-1}$$. Now consider pairs $$(t,t')$$ which are in the given range and differ by at most $$10$$. There are roughly $$n^{1/2}$$ such pairs (as opposed to about $$n$$ such pairs with no restriction on the difference) so the expected number of pairs of vertices with in-degree in the given range and differing by at most $$10$$ is something like $$n^{-1/2}$$. In particular, it's likely there is no such pair.

And in particular, it's likely the vertex with minimum in-degree is unique; the next smallest in-degree is likely more than $$10$$ larger.

For a proper proof of this last (not cheating on independence; the rest of the argument is rigorous), see Frieze and Karonski's book 'Random Graphs'; this is in the 'degrees of dense random graphs' section.

Maybe it's interesting to note that the answer is very different for the minimum score. With probability about $$\tfrac12$$ (and this is the limit) the minimum in-degree is smaller than any out-degree, and hence all but one vertex ($$z$$) have the same minimum score. When the minimum out-degree is smaller than the minimum in-degree, it's likely unique (as above) and hence the minimum score vertex is unique. It's unlikely that the minimum in-degree and minimum out-degree are the same.

• Chernoff plus Union bound say that the statement holds for all pairs of disjoint subsets of this size, in particular for any choice of S you make. – user36212 Mar 1 '20 at 16:51
• No, but the proof goes through with tiny changes. – user36212 Mar 2 '20 at 7:00