论文标题
占主导地位的锦标赛家庭
Dominant tournament families
论文作者
论文摘要
对于带有$ h $顶点的比赛$ h $，其典型密度为$ h！2^{ - \ binom {h} {2}}}}/aut（h）$，即，这是随机锦标赛中$ h $的预期密度。 $ h $ -vertex锦标赛的家庭$ {\ mathcal f} $是{\ em占主导地位}如果对于所有足够大的$ n $，则存在$ n $ vertex toram $ g $，因此$ {\ nathcal f} $ g $ g $的每个元素的密度都比其典型的典型dentstalt taustmant vasters tasters factors factors。表征所有主导家庭的表征已经对小$ h $挑战。在这里，我们每$ h $都表征了几个大型统治家庭。特别是，我们证明了所有$ h $的以下内容：（i）对于所有锦标赛$ h^*$，至少$ 5 \ log h $ Vertices，所有$ h $ vertex锦标赛的家族都包含$ h^*$作为子段的$ h^*$。 （ii）所有$ h $ vertex锦标赛的家族的最低反馈弧设置大小最多为$ \ frac {1} {2} {2} \ binom {h} {2} {2} -h^{3/2} {3/2} \ sqrt {\ sqrt {\ ln H} $是统治。对于小$ h $，我们建立了一个$ 6 $（即$ 50 \％$ $ 50 $）的主要家庭，上面$ 5 $顶点和大小的主要家庭家庭，大于$ 40 \％\％$ $ h = 6,7,8,9 $。对于所有$ h $，我们提供了一个显性家庭的明确结构，该构造旨在在$ h $顶点上获得绝对恒定的锦标赛。提出了一些其他有趣的开放问题。
For a tournament $H$ with $h$ vertices, its typical density is $h!2^{-\binom{h}{2}}/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 $5\log 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 $\frac{1}{2}\binom{h}{2}-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.
