6
$\begingroup$

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.

$\endgroup$

1 Answer 1

10
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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