Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.03234 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918186988863488 |
|---|---|
| author | Kim, Seokbeom LaGrange, Taite Rundström, Mathieu Sadhukhan, Arpan Spirkl, Sophie |
| author_facet | Kim, Seokbeom LaGrange, Taite Rundström, Mathieu Sadhukhan, Arpan Spirkl, Sophie |
| contents | We extend the list of tournaments $S$ for which the complete structural description for tournaments excluding $S$ as a subtournament is known. Specifically, let $Δ(1, 2, 2)$ be a tournament on five vertices obtained from a cyclic triangle by substituting a two-vertex tournament for two of its vertices. In this paper, we show that tournaments excluding $Δ(1, 2, 2)$ as a subtournament are either isomorphic to one of three small tournaments, obtained from a transitive tournament by reversing edges in vertex-disjoint directed paths, or obtained from a smaller tournament with the same property by applying one of two operations. In particular, one of these operations creates a homogeneous set that induces a subtournament isomorphic to one of three fixed tournaments, and the other creates a homogeneous pair such that their union induces a subtournament isomorphic to a fixed tournament. As an application of this result, we present an upper bound for the chromatic number, a lower bound for the size of a largest transitive subtournament, and a lower bound for the number of vertex-disjoint cyclic triangles for such tournaments. The bounds that we present are all best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03234 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The structure of $Δ(1, 2, 2)$-free tournaments Kim, Seokbeom LaGrange, Taite Rundström, Mathieu Sadhukhan, Arpan Spirkl, Sophie Combinatorics We extend the list of tournaments $S$ for which the complete structural description for tournaments excluding $S$ as a subtournament is known. Specifically, let $Δ(1, 2, 2)$ be a tournament on five vertices obtained from a cyclic triangle by substituting a two-vertex tournament for two of its vertices. In this paper, we show that tournaments excluding $Δ(1, 2, 2)$ as a subtournament are either isomorphic to one of three small tournaments, obtained from a transitive tournament by reversing edges in vertex-disjoint directed paths, or obtained from a smaller tournament with the same property by applying one of two operations. In particular, one of these operations creates a homogeneous set that induces a subtournament isomorphic to one of three fixed tournaments, and the other creates a homogeneous pair such that their union induces a subtournament isomorphic to a fixed tournament. As an application of this result, we present an upper bound for the chromatic number, a lower bound for the size of a largest transitive subtournament, and a lower bound for the number of vertex-disjoint cyclic triangles for such tournaments. The bounds that we present are all best possible. |
| title | The structure of $Δ(1, 2, 2)$-free tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.03234 |