Unavoidable Subtournaments in Large Tournaments with No Homogeneous Sets

2017 
A loopless digraph is a tournament if for every pair of distinct vertices $u$ and $v$, exactly one of $uv$ and $vu$ is an edge. For a tournament $T$, a set $S\subseteq V(T)$ is homogeneous if every vertex $v$ outside of $S$ is either complete to $S$ or complete from $S$. A tournament is prime if for every homogeneous set $S$ of $T$, either $|S| \le 1$ or $S=V(T)$. In this paper, we present a list of eight classes of prime tournaments and prove that for every positive integer $n$, there exists $N$ such that every prime tournament of size at least $N$ contains a prime tournaments from the list of size at least $n$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    0
    References
    1
    Citations
    NaN
    KQI
    []