EUVIMEDEUVIMED entdecken
Crossref

Blow-Ups and Extensions of Trees in Tournaments

Pierre Aboulker, Frédéric Havet, William Lochet, Raul Lopes, Lucas Picasarri-Arrieta, Clément Rambaud

The Electronic Journal of Combinatorics · 07.08.2026 · 33 (3)

DOI: 10.37236/13540 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 07.08.2026. Verfasst von Pierre Aboulker und 5 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A class of acyclic digraphs $\mathcal{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathcal{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly unavoidable, and Fox, He, and Wigderson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Häggkvist and Thomason proved that the class of oriented trees is linearly unavoidable. In this work, we generalize this result to acyclic digraphs obtained from an oriented tree by adding at most $k$ vertices, and $k$-blow-ups of oriented trees, for every fixed integer $k$. More precisely, we show that if $D$ is obtained from an oriented tree $F$ of sufficiently large order $n$ by adding $k$ universal vertices, then $D$ is contained in all tournaments on $2\cdot 3^{(k+1)(2k+1)} \cdot n$ vertices; and if $D$ is obtained from $F$ by replacing each vertex $u$ by an independent set $X_u$ of size $k$ and every arc $uv$ by all possible arcs from $X_u$ to $X_v$, then $D$ is contained in every tournament on $2^{10+18k}k \cdot n$ vertices.

Zitieren

APA

Aboulker, P., Havet, F., Lochet, W., Lopes, R., Picasarri-Arrieta, L., & Rambaud, C. (2026). Blow-Ups and Extensions of Trees in Tournaments. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/13540

Vancouver

Aboulker P, Havet F, Lochet W, Lopes R, Picasarri-Arrieta L, Rambaud C. Blow-Ups and Extensions of Trees in Tournaments. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/13540

BibTeX
@article{Aboulker2026,
  author = {Aboulker, Pierre and Havet, Frédéric and Lochet, William and Lopes, Raul and Picasarri-Arrieta, Lucas and Rambaud, Clément},
  title = {Blow-Ups and Extensions of Trees in Tournaments},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {3},
  doi = {10.37236/13540}
}
Kostenlos starten →