Dominant tournament families

For a tournament $H$ with $h$ vertices, its typical density is given by $h!2^{-(\frac{h}{2})} / \operatorname{aut}(H)$, i.e. this is the expected density of $H$ in a random tournament. A family $\mathcal{F}$ of $h$-vertex tournaments is dominant if for all sufficiently large $n$, there exists an $n$-vertex tournament $G$ such that the density of each element of $\mathcal{F}$ in $G$ is larger than its typical density by a constant factor. Characterizing all dominant families is challenging already for small $h$. Here we characterize several large dominant families for every $h$. In particular, we prove the following for all $h$ sufficiently large: (i) For all tournaments $H^\ast$ with at least $5 \operatorname{log} h$ vertices, the family of all $h$-vertex tournaments that contain $H^\ast$ as a subgraph is dominant. (ii) The family of all $h$-vertex tournaments whose minimum feedback arc set size is at most $\frac{1}{2} {\left ( {}^h_2 \right )} - h^{3/2} \sqrt{\ln h}$ is dominant. For small $h$, we construct a dominant family of $6$ (i.e. 50% of the) tournaments on $5$ vertices and dominant families of size larger than 40% for $h = 6, 7, 8, 9$. For all $h$, we provide an explicit construction of a dominant family which is conjectured to obtain an absolute constant fraction of the tournaments on $h$ vertices. Some additional intriguing open problems are presented.

Keywords

tournament, density

2010 Mathematics Subject Classification

05C20, 05C35

Full Text (PDF format)

The author’s research was supported by the Israel Science Foundation (grant No. 1082/16).

Received 29 March 2020

Accepted 14 June 2020

Published 16 July 2021