Large dominating sets in tournaments 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.) 
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.
 A: All logarithms are base-$2$ here.


*

*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].

*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.

*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.
