Trees with few leaves in tournaments

Alistair Benford, Richard Montgomery

Abstract

We prove that there exists $C>0$ such that any $(n+Ck)$-vertex tournament contains a copy of every $n$-vertex oriented tree with $k$ leaves, improving the previously best known bound of $n+O(k^2)$ vertices to give a result tight up to the value of $C$. Furthermore, we show that, for each $k$, there exists $n_0$, such that, whenever $n\geqslant n_0$, any $(n+k-2)$-vertex tournament contains a copy of every $n$-vertex oriented tree with at most $k$ leaves, confirming a conjecture of Dross and Havet.

Introduction

In extremal graph theory, a tournament is a complete graph where every edge is assigned a direction. A fundamental question in this field is determining the minimum size of a tournament required to guarantee the existence of a specific oriented tree (a directed graph whose underlying structure is a tree).

The difficulty of embedding these trees varies significantly based on their structure. For instance, oriented paths—trees with only two leaves—are relatively straightforward to find; a tournament of size $n$ is typically sufficient. Conversely, stars—where a single root connects to $n-1$ leaves—represent the most difficult cases. Sumner’s conjecture (1971) posits that $2n-2$ vertices are necessary to guarantee the presence of any $n$-vertex tree. This research addresses the gap between these two extremes, focusing on how the number of leaves ($k$) dictates the required tournament size.

The Complexity of Leaves

Previous literature established that the number of additional vertices needed to embed an $n$-vertex tree was $O(k^2)$. This quadratic relationship suggested that as trees became "bushier," the difficulty of embedding them grew rapidly. Benford and Montgomery sought to refine this bound, aiming for a linear relationship ($O(k)$) and, ultimately, the optimal bound for sufficiently large trees.

Their work reinforces the insight that the "leaf count" is the primary driver of complexity in tournament embeddings. By moving from a quadratic bound to a linear one, the authors demonstrate that the "cost" of adding a leaf to a tree is essentially constant relative to the required tournament size.

Key Results

Theorem 1.1: The Linear Bound

The authors prove the existence of a constant $C > 0$ (specifically $C < 500$) such that any tournament with $n + Ck$ vertices contains every $n$-vertex oriented tree with $k$ leaves. This result significantly narrows the search space for embedding and provides a much tighter bound than previous $O(k^2)$ estimates.

Theorem 1.2: The Optimal Bound (Dross-Havet Conjecture)

For every $k$, there exists a threshold $n_0$ such that if $n \ge n_0$, any tournament with $n + k - 2$ vertices is guaranteed to contain every $n$-vertex oriented tree with at most $k$ leaves. This confirms the Dross and Havet conjecture, establishing the absolute limit for the problem in the case of large trees.

Methodological Innovations

The proof relies on a sophisticated "divide and conquer" strategy centered on median orders. A median order is a specific arrangement of a tournament's vertices that maximizes the number of edges pointing forward in the sequence.

Key technical components include:

  • Tree Decomposition: Large trees are broken down into "good decompositions" consisting of long directed paths and smaller subtrees.
  • Absorption Paths: The authors utilize a technique from extremal combinatorics where a specific path in the tournament is designed to be "flexible." This path can "absorb" or skip extra vertices as needed to ensure the embedding terminates at the required vertex.
  • Probabilistic Foundations: While the final result is deterministic, the proof uses random vertex selection to demonstrate that robust structures, such as absorption paths, must exist within the tournament with positive probability.
  • Median Order Properties: The authors exploit the fact that in a median order, any two vertices can be connected by very short directed paths (length 3), even when avoiding a set of "forbidden" vertices. This allows for precise "slotting" of tree components into specific regions of the tournament.

Discussion and Future Work

While this paper represents a major breakthrough, several avenues for refinement remain:

  1. Optimizing the Constant: Although the authors prove $C < 500$, they did not attempt to find the smallest possible value for $C$. Future research may significantly reduce this constant.
  2. The Threshold $n_0$: The proof for the optimal bound (Theorem 1.2) requires $n$ to be exponential in $k$ ($k^{O(k)}$). The authors conjecture that a much smaller threshold, perhaps linear in $k$ ($n_0 = O(k)$), might be sufficient.
  3. Small $n$ Cases: The optimal bound of $n+k-2$ is currently only guaranteed for large $n$. The behavior of these embeddings for small $n$ and $k$ remains an open question in the field.

Summary updated

Abstract

We prove that there exists $C&gt;0$ such that any $(n+Ck)$-vertex tournament contains a copy of every $n$-vertex oriented tree with $k$ leaves, improving the previously best known bound of $n+O(k^2)$ vertices to give a result tight up to the value of $C$. Furthermore, we show that, for each $k$, there exists $n_0$, such that, whenever $n\geqslant n_0$, any $(n+k-2)$-vertex tournament contains a copy of every $n$-vertex oriented tree with at most $k$ leaves, confirming a conjecture of Dross and Havet.
BibTeX
@article{benford2022trees,
  author = {Alistair Benford and Richard Montgomery},
  title = {{Trees with few leaves in tournaments}},
  journal = {Journal of Combinatorial Theory Series B},
  year = {2022},
  doi = {10.1016/j.jctb.2022.02.005},
}
Figure