Impartial digraphs (Q2663414)

In this paper a conjecture of Fox, Huang, and Lee is proved that characterizes directed graphs having constant density in all tournaments. A digraph \(\overrightarrow{H}\) is said to be impartial if it has the following property. For some \(n\) at least the order of \(\overrightarrow{H}\), all \(n\)-vertex tournaments contain the same number of copies of \(\overrightarrow{H}\) as subgraphs. A digraph \(\overrightarrow{T}\) is said to be recursively bridge-mirrored if it can be constructed recursively in the following manner from a single vertex. Mark an arbitrary vertex of \(\overrightarrow{T}\) as its root, and create a new graph by taking two identical copies of this rooted \(\overrightarrow{T}\) and adding a new directed edge from one root to the other. The main theorem established is the following equivalence. A directed graph is impartial if and only if it is a disjoint union of recursively bridge-mirrored digraphs.