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$ Commented Apr 15, 2017 at 16:21
  • $\begingroup$ I got to $klogn -\frac{n}{2^{k-1}} \lt \frac{-k}{2^{k-1}}$ $\endgroup$ Commented 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
    Commented 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$ Commented Apr 17, 2017 at 14:59
  • $\begingroup$ You can increase the value of $n$ suitably so that it works for all $k$. $\endgroup$
    – Aravind
    Commented Apr 17, 2017 at 16:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .