Definitions:
- Tournament and Dominating set
- In a tournament $T$, for $u,v \in V(T)$, an edge “$u \rightarrow v$” means $u$ defeats $v$.
- We say $T$ has the Schütte property $S_{k}$ if it has no dominating set of size at most $k$
- Let $\sigma(k)$ be the minimum number of vertices in a tournament with the property $S_{k}$
I need to show that $\sigma(k) = \Omega(k2^k)$, i.e. any tournament on $k2^k$ vertices would have a dominating set of size at most $k$ . I’m trying a probabilistic argument below, but it turns out to be valid for any positive bound, and I can’t see where it went wrong.
Proof:
- For every pair $x,y \in V(T)$, choose $x \rightarrow y$ or $y \rightarrow x$ uniformly at random.
- Given a set $S \in\left(\begin{array}{c}{[k2^k]} \\ k\end{array}\right),$ let $E_{S}$ be the event that $S$ is a dominating set.
- For $S$ to dominate a fixed vertex $v$, cannot have all edges $v \rightarrow S$
- $k$ edges, chosen independently $\Rightarrow$ probability is $1-2^{-k}$
- This must be true for all vertices in $V(T) \backslash S$
- Edges again independent $\Rightarrow \mathbb{P}\left(E_{S}\right)=\left(1-2^{-k}\right)^{k2^k – k}$
- Consider $\sum_{S} \mathbb{P}\left(E_{S}\right)$. If this quantity is positive, then at least one of the $\mathbb{P}(E_S)$ is positive.
- But indeed $\sum_{S} \mathbb{P}\left(E_{S}\right)= {{k2^k} \choose k}\left(1-2^{-k}\right)^{k2^k – k} > 0$.
===================================================================
Edit: I’m still stuck, but have come up with several ideas. Would like to hear if any of those could be developed further.
$\ $
Proof attempt 1: I’ve computed that, in a tournament on $[n]$ vertices, the total out-degree of all $k$-sets is $\frac{1}{2} {n \choose k} k(n-k)$, and so the average out-degree of the $k$-sets is $\frac{1}{2}k(n-k)$.
Assume for a contradiction that a tournament $T$ on $k2^k$ doesn’t have a dominating set of size at most $k$, and let $S$ be a $k$-set of maximum out-degree, and $v$ is a vertex in $V(T) \setminus S$ that dominates $S$.
By the above, the out-degree of $S$ must be at least $\frac{1}{2}k(n-k)$, and I’m trying to see if another $k$-set with larger out-degree exists, hence contradiction.
$\ $
Proof attempt 2: I’m trying a constructive proof to find a dominating set of size $k$ in the tournament $T$, with $V(T) = k2^k$, by repeated applications of the pigeon-hole principle.
Since the average out-degree of a vertex is $\frac{1}{2}(k2^k -1)$, for a vertex $v_1$ of maximum out-degree, the size of the set of vertices that dominates $v_1$ must be at most $k2^k – \frac{1}{2}(k2^k -1) – 1 = \frac{1}{2}(k2^k -1)$. From this set of vertices, we can find a vertex $v_2$ of maximum out-degree (w.r.t. this set of vertices), and so on.
I was hoping to construct a sequence of dominating set this way, but it turns out that I’d need to pick more than $k$ vertices before the size of the remaining vertices becomes less than $1$.
Best Answer
You've shown that in a random tournament, $\sum_{S} \mathbb{P}\left(E_{S}\right) > 0$. (Incidentally, looking at the sum is unnecessary to see that $\mathbb{P}(E_S)$ is positive: you have a formula for $\mathbb{P}(E_S)$.)
When looking at an arbitrary tournament, you're not allowed to say that the probability of having edges $v \to s$ for all $s \in S$ is $2^{-k}$. Once you've chosen $S$, those edges are what they are. Your only possible source of randomness is in the choice of $S$.
In general, my advice when writing a probabilistic proof would be to begin by saying what exactly you're choosing at random, and from what distribution.