2
$\begingroup$

A dominated set is a set of vertices $S$ in a tournament $T$ such that there is a vertex $v\in T\setminus S$ that points at all the vertices in S

  1. Show that every tournament on $2^k$ vertices contains a set of at most $k$ vertices that is not dominated

  2. Show that if $\binom{n}{k}(1-\frac{1}{2^k})^{n-k} \lt 1$
    then there is an $n$-vertex tournament so that every set of $k$ vertices is dominated

  3. Use 2 to get an explicit estimate for the size of the smallest tournament in which every $k$-set is dominated

I have solved part 1 of the question, but don't know how to approach 2 and 3

$\endgroup$

1 Answer 1

0
$\begingroup$

For part 2, use the probabilistic method. For each pair of vertices $\{x,y\}$, orient the edge from $x$ to $y$ with probability 1/2 and from $y$ to $x$ with probability 1/2. For each set of size $k$, calculate the probability that it is not dominated and then use the union bound.

For part 3, we use the following two inequalities: $\dbinom{n}{k} \leq {\left( \dfrac{en}{k}\right)}^k$ and $1-x \leq e^{-x}$.

Thus, sufficient is that: $\left(\dfrac{en}{k}\right)^k e^{-\frac{(n-k)}{2^k}}<1$.

To achieve this, we set $n=k^22^k+k$.

The L.H.S. is then at most $\left(e(k2^k+1)\right)^ke^{-k^2}$, which is less than 1 for sufficiently large $k$ because the first term is dominated by $2^{k^2}$ essentially which is smaller than $e^{k^2}$.

$\endgroup$
8
  • $\begingroup$ Im still not able to extract n from the equation using these inequalities $\endgroup$ Apr 15, 2017 at 16:21
  • $\begingroup$ I got to $klogn -\frac{n}{2^{k-1}} \lt \frac{-k}{2^{k-1}}$ $\endgroup$ Apr 17, 2017 at 9:08
  • $\begingroup$ I am sorry; to get a sufficient condition, we need the other direction; I'll update the answer. $\endgroup$
    – Aravind
    Apr 17, 2017 at 11:06
  • $\begingroup$ Im still not sure I understand, dont I need to give a bound on n for a given k? and not a bound for large enough k? $\endgroup$ Apr 17, 2017 at 14:59
  • $\begingroup$ You can increase the value of $n$ suitably so that it works for all $k$. $\endgroup$
    – Aravind
    Apr 17, 2017 at 16:59

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.