Regular tournaments missing near-complete balanced antidirected trees
Note on near-spanning balanced antidirected trees missing from regular tournaments
Discrete Mathematics
Summary
The paper shows that certain highly symmetric directed graphs called regular tournaments can fail to contain almost all of a particular kind of tree, called balanced antidirected trees, despite meeting expected degree conditions that should allow such embeddings. Specifically, the authors construct examples where a large tournament cannot fit a balanced antidirected caterpillar tree that is just one vertex short of spanning it. This counters some existing conjectures about the conditions needed for such embeddings. The work also includes a small specific example with a double-star tree and a Paley tournament.
What this means in practice
- •For network designers: Identify limitations in embedding certain balanced directed tree structures within highly symmetric network topologies.
- •For graph algorithm developers: Design algorithms accounting for cases where common semidegree conditions do not guarantee spanning antidirected tree embeddings in symmetric digraphs.
A theory result. No direct application yet.
Authors
Gregory Gutin, Yiming Hao
Abstract
We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer $n$, we exhibit a regular vertex-transitive tournament on $n$ vertices and a balanced antidirected caterpillar on $n-1$ vertices with maximum degree at most $(1+o(1))n/\log_2 n$ that is not contained in the tournament. The host satisfies the strict $k/2$ threshold in both the semidegree and pseudo-semidegree settings, where $k$ is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order $n-1$ of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.