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

The full text of this article is unavailable through your IP address: 3.145.85.233

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