Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.23566 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912097091190784 |
|---|---|
| author | Aboulker, Pierre Havet, Frédéric Lochet, William Lopes, Raul Picasarri-Arrieta, Lucas Rambaud, Clément |
| author_facet | Aboulker, Pierre Havet, Frédéric Lochet, William Lopes, Raul Picasarri-Arrieta, Lucas Rambaud, Clément |
| contents | A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Thomason and Häggkvist 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 order $n$ by adding $k$ universal vertices, then $D$ is contained in every tournament of order $2\cdot 3^{(k+1)(2k+1)} \cdot n$; 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 of order $2^{10+18k}k \cdot n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23566 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Blow-ups and extensions of trees in tournaments Aboulker, Pierre Havet, Frédéric Lochet, William Lopes, Raul Picasarri-Arrieta, Lucas Rambaud, Clément Combinatorics A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Thomason and Häggkvist 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 order $n$ by adding $k$ universal vertices, then $D$ is contained in every tournament of order $2\cdot 3^{(k+1)(2k+1)} \cdot n$; 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 of order $2^{10+18k}k \cdot n$. |
| title | Blow-ups and extensions of trees in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.23566 |