For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.

Is it true that for every subtournament $T$ of $T_q$ we have $\mathrm{dom}(T)\leq \mathrm{dom}(T_q)$?

There is quite a bit of research regarding bounds on $\mathrm{dom}(T_q)$, but I haven't found anything which is along the lines of my question -- where the actual value of $\mathrm{dom}(T_q)$ is irrelevant.

A good overview of what is known about the order of the smallest dominating sets in Paley tournaments can be found here Large dominating sets in tournaments and here https://www.win.tue.nl/~aeb/graphs/Paley.html


As suggested in the comments, let me state a more general version of my question. First, let's say that $S$ is an out-dominating set in $T$ if for all $v\in V(T)\setminus S$, there exists $u\in S$ such that $(u,v)\in E(T)$ and $S$ is an in-dominating set in $T$ if for all $v\in V(T)\setminus S$, there exists $u\in S$ such that $(v,u)\in E(T)$. Now define $\mathrm{dom}^+(T)$ to be the order of a smallest out-dominating set (compared to what I wrote above, $\mathrm{dom}^+$ and $\mathrm{dom}$ mean the same thing) and $\mathrm{dom}^-(T)$ to be the order of a smallest in-dominating set.

Is it true that for infinitely many $k\geq 2$, there exists a tournament $T$ such that $\mathrm{dom}^-(T)=k$ and for all $T'\subseteq T$, $\mathrm{dom}^+(T')\leq k$.

This would be implied by my more specific first question because if $T_q$ is a Paley tournament, then $\mathrm{dom}^+(T_q)=\mathrm{dom}^-(T_q)$ and for all $m\geq 2$, there exists $q$ such that $\mathrm{dom}^-(T_q)\geq m$.

A result of E. Szekeres and G. Szekeres says that if $|V(T)|<(k+2)2^{k-1}-1$, then $\mathrm{dom}^+(T)\leq k$. Since $\mathrm{dom}^-(T_7)=3$ and $\mathrm{dom}^-(T_{19})=4$, the result of Szekeres and Szekeres implies a positive answer to the general question for $k=2$ and $k=3$ (and the original question for $q=7$ and $q=19$).

  • $\begingroup$ It seems quite unlikely that one could prove such a result. If it is false, disproving it also seems quite hard too, as dominating number is not particularly tractable quantity. What is the reason for your question? Perhaps there is an approach avoiding this question. $\endgroup$
    – Boris Bukh
    Feb 8, 2021 at 14:00
  • $\begingroup$ Since the answer I formulated was longer than my original post, I answered your question by updating the post. $\endgroup$
    – Louis D
    Feb 8, 2021 at 19:07

1 Answer 1


This is a construction answering the updated question. The original problem looks much, much harder.

Let $N$ be very large in terms of $k$. Let $M=kN$ The vertex set of the tournament is $\mathbb{Z}/M\mathbb{Z}$. There are two kinds of edges. First, there are edges from $x$ to each of $x+1,x+2,x+3,\dotsc,x+N$. We call these circular edges. For each pair $x,y$ not connected by a circular edge, we choose the direction of the edge connecting $x$ and $y$ uniformly at random.

Note that the definition of the tournament is invariant under reversal of the arrows and reversal of the circular direction. So, I will speak of the ``domination number'' instead of in-domination and out-domination.

The domination number of every subtournament is at most $k$. Indeed, let $U$ be the vertex set of the subtournament. Let $x_1=\min U$, and then define inductively $x_{i+1}=\min U\setminus \{1,2,\dotsc,x_i+N\}$. It is clear then that $\{x_1,\dotsc,x_k\}$ is a dominating set (which could be of size smaller than $k$ if we run out of elements sooner).

I claim that the domination number of the tournament is at least $k$. Indeed, let $X=\{x_1,\dotsc,x_{k-1}\}$ be any $(k-1)$-element set of vertices, and let $R=X+\{1,2,\dotsc,N\}$ be the set of the vertices connected to them by circular outedges. Then $S=V(T)\setminus R$ is a set of size at least $N-k$. Let's compute the probability that $S$ is dominated by $X$ via non-circular (=random) edges. Well, that probability is simply $(1-2^{-(k-1)})^{|S|}<\exp\bigl(-2^{-(k-1)}(N-k)\bigr)$. If $N=4^k$, say, then this is much less than $\binom{M}{k-1}^{-1}$, and so the claim follows by the union bound over all $(k-1)$-element sets $X$.

  • $\begingroup$ Mixing the deterministic edges with the random construction is a beautiful idea. Thank you! $\endgroup$
    – Louis D
    Feb 9, 2021 at 1:56

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.