Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.03634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912521632350208 |
|---|---|
| author | Hunter, Zach Liu, Teng Milojević, Aleksa Sudakov, Benny |
| author_facet | Hunter, Zach Liu, Teng Milojević, Aleksa Sudakov, Benny |
| contents | Let $G$ be a Dirac graph, and let $S$ be a vertex subset of $G$, chosen uniformly at random. How likely is the induced subgraph $G[S]$ to be Hamiltonian? This question, proposed by Erdős and Faudree in 1996, was recently resolved by Draganić, Keevash and Müyesser, in the setting of graphs. In this paper, we study a similar question for tournaments -- if $T$ is a tournament of high minimum degree, how likely is it for a random induced subtournament of $T$ to be Hamiltonian? We prove an optimal bound on this probability, and extend the results to the regime where the subset is not sampled uniformly at random, but according to a $p$-biased measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_03634 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cyclic subsets of tournaments Hunter, Zach Liu, Teng Milojević, Aleksa Sudakov, Benny Combinatorics Let $G$ be a Dirac graph, and let $S$ be a vertex subset of $G$, chosen uniformly at random. How likely is the induced subgraph $G[S]$ to be Hamiltonian? This question, proposed by Erdős and Faudree in 1996, was recently resolved by Draganić, Keevash and Müyesser, in the setting of graphs. In this paper, we study a similar question for tournaments -- if $T$ is a tournament of high minimum degree, how likely is it for a random induced subtournament of $T$ to be Hamiltonian? We prove an optimal bound on this probability, and extend the results to the regime where the subset is not sampled uniformly at random, but according to a $p$-biased measure. |
| title | Cyclic subsets of tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.03634 |