3
$\begingroup$

Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the vertices in $S$?

Note that $v$ can be in $S$. Also, we assume that each vertex has an incoming edge from itself.

$\endgroup$
3
  • $\begingroup$ Can't you choose $S$ to contain a single vertex? You probably want to exclude that case. $\endgroup$ Commented Dec 31, 2023 at 16:50
  • $\begingroup$ @CommandMaster it probably does not work for $v$ not in $S$ $\endgroup$ Commented Dec 31, 2023 at 17:39
  • $\begingroup$ @bof Thanks, I have updated the question to rule out $S=\emptyset$. By complete directed graph I mean a complete graph whose edges are directed; directed complete graph is a better term. $\endgroup$ Commented Jan 1, 2024 at 7:41

1 Answer 1

4
$\begingroup$

Not always. I claim that for large $n$ a random tournament on $n$ vertices satisfies your property with probability tending to 0.

We use the following

Lemma. Consider a random tournament on $m$ vertices $1,\ldots,m$. For a given sequence $(d_1,\ldots,d_m)$ the probability that $\deg(i)=d_i$ for all $i=1,2,\ldots,m$ is at most $\exp(-cm\log m)$ (for a universal constant $c$).

Proof. Fix what happens between the first $m_1:=\lceil m/2\rceil$ vertices. Then the event that these $m_1$ vertices have prescribed degrees is an intersection of $m_1$ independent events (corresponding to these vertices) each of which has probability at most $O(m^{-1/2})$ (by de Moivre — Laplace local central limit theorem: each event for a fixed vertex is that the sum of $m-m_1$ independent 0-1's has prescribed value).

Return to your problem. The probability that a given set $S$ satisfies your condition for all $v\notin S$ is at most $(1/2)^{n-|S|}$. The sum over all $S$ of size, say, less than $n/10$, is clearly $o(1)$. For $|S|\geqslant n/10$ we look at vertices $v\in S$, that is, we are interested only in a random tournament induced on $S$. I claim that the probability that it satisfies your requirement is $o(1/2^n)$, that suffices for my initial claim.

Denote $m=|S|$. Your requirement yields that the indegree of each vertex $v\in S$ is at least $m/2-1$. If $m$ is odd, this means that the indegree is at least $(m-1)/2$, thus all indegrees are equal to $(m-1)/2$ (since it is the average indegree), and we just apply Lemma. If $m=2m_1$ is even, then all indegrees must be at least $m_1-1$. Enumerate $S$ and denote the indegrees $m_1-1+\varepsilon_i$ ($i=1,2,\ldots,2m_1$). Then $\sum \varepsilon_i=m_1$. Such a sequence of non-negative $\varepsilon_i$'s may be chosen by ${3m_1-1\choose 2m_1-1}$ ways, which is only exponential in $m$, while the Lemma says that for a fixed degree sequence the probability that it arises in a random tournament is superexponentially small.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.