Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.04636 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909185677983744 |
|---|---|
| author | Benford, Alistair DeBiasio, Louis Larson, Paul |
| author_facet | Benford, Alistair DeBiasio, Louis Larson, Paul |
| contents | We prove a strong dichotomy result for countably-infinite oriented graphs; that is, we prove that for all countably-infinite oriented graphs $G$, either (i) there is a countably-infinite tournament $K$ such that $G\not\subseteq K$, or (ii) every countably-infinite tournament contains a \emph{spanning} copy of $G$. Furthermore, we are able to give a concise characterization of such oriented graphs. Our characterization becomes even simpler in the case of transitive acyclic oriented graphs (i.e. strict partial orders).
For uncountable oriented graphs, we are able to extend the dichotomy result mentioned above to all regular cardinals $κ$; however, we are only able to provide a concise characterization in the case when $κ=\aleph_1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_04636 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Unavoidable structures in infinite tournaments Benford, Alistair DeBiasio, Louis Larson, Paul Combinatorics Logic We prove a strong dichotomy result for countably-infinite oriented graphs; that is, we prove that for all countably-infinite oriented graphs $G$, either (i) there is a countably-infinite tournament $K$ such that $G\not\subseteq K$, or (ii) every countably-infinite tournament contains a \emph{spanning} copy of $G$. Furthermore, we are able to give a concise characterization of such oriented graphs. Our characterization becomes even simpler in the case of transitive acyclic oriented graphs (i.e. strict partial orders). For uncountable oriented graphs, we are able to extend the dichotomy result mentioned above to all regular cardinals $κ$; however, we are only able to provide a concise characterization in the case when $κ=\aleph_1$. |
| title | Unavoidable structures in infinite tournaments |
| topic | Combinatorics Logic |
| url | https://arxiv.org/abs/2301.04636 |