# Dominating sets in subtournaments of the Paley tournament

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

Update:

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$$).

• 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. – Boris Bukh Feb 8 at 14:00
• Since the answer I formulated was longer than my original post, I answered your question by updating the post. – Louis D Feb 8 at 19:07

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