2020/06/19 by Raphael Yuster, Yuster, Raphael
Mathematics · #05C20 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2006.11076
openalex publication_date 2020/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a tournament H with h vertices, its typical density is h!2^-\binomh2/aut(H), i.e. this is the expected density of H in a random tournament. A family \mathcal F of h-vertex tournaments is \em 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^* with at least 5log h vertices, the family of all h-vertex tournaments that contain H^* as a subgraph is dominant. (ii) The family of all h-vertex tournaments whose minimum feedback arc set size is at most (1)/(2)\binomh2-h3/2√(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.