It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log\_2 n\rceil$. (See Fact 2.5 [here](http://theory.stanford.edu/~megiddo/pdf/uzx.pdf).) 


What are tournaments such that any dominating set is of size $\Omega(\log n)$? No example is given in the link above. A tournament that does *not* work is one where the vertices are on a cycle and each vertex has an edge to $(n-1)/2$ following vertices clockwise -- in this case taking two opposite vertices already gives a dominating set.



Large dominating sets in tournaments
All logarithms are base-$2$ here.


1. With high probability, a random tournament has no dominating sets of size $k\approx\log n-2\log\log n$, as shown by Erdős [1].
2. Paley tournaments: if $q\equiv3\pmod4$ is a prime power, define a tournament whose vertex set is the finite field $\mathbb F\_q$ by
$$x\to y\iff y-x\text{ is a square in }\mathbb F\_q.$$
Graham and Spencer [2] proved that the Paley tournament has no dominating sets of size $k\approx\frac12\log q-\log\log q$, as a consequence of Weil’s bound on character sums.
3. Blass and Rossman [3] gave a somewhat complicated, but explicit construction of a tournament with an elementary proof that it has no dominating sets of size $k\approx(\log n)^{1/4}$.


In all these examples, the tournaments actually have stronger properties: they satisfy the extension axioms up to size $k$ (i.e., whenever you select a set of $k$ vertices, and prescribe for each of them individually whether it wins or loses, there exists a vertex that fits these constraints).


**References:**


[1] Paul Erdős: *On a problem in graph theory,* Mathematical Gazette 47 (1963), no. 361, pp. 220-223.


[2] Ronald L. Graham, Joel H. Spencer: *A constructive solution to a tournament problem,* Canadian Mathematical Bulletin 14 (1971), no. 1, pp. 45-48.


[3] Andreas Blass, Benjamin Rossman: *Explicit graphs with extension properties*, Bulletin of the EATCS 86 (2005), pp. 166–175.


