The Library
Trees with many leaves in tournaments
Tools
Tools
Tools
Benford, Alistair and Montgomery, Richard (2022) Trees with many leaves in tournaments. (Submitted)
|
PDF
WRAP-Trees-with-many-leaves-tournaments-22.pdf - Submitted Version - Requires a PDF viewer. Download (909Kb) | Preview |
Abstract
Sumner's universal tournament conjecture states that every (2n−2)-vertex tournament should contain a copy of every n-vertex oriented tree. If we know the number of leaves of an oriented tree, or its maximum degree, can we guarantee a copy of the tree with fewer vertices in the tournament? Due to work initiated by Häggkvist and Thomason (for number of leaves) and Kühn, Mycroft and Osthus (for maximum degree), it is known that improvements can be made over Sumner's conjecture in some cases, and indeed sometimes an (n+o(n))-vertex tournament may be sufficient.
In this paper, we give new results on these problems. Specifically, we show
i) for every α>0, there exists n0∈N such that, whenever n⩾n0, every ((1+α)n+k)-vertex tournament contains a copy of every n-vertex oriented tree with k leaves, and
ii) for every α>0, there exists c>0 and n0∈N such that, whenever n⩾n0, every (1+α)n-vertex tournament contains a copy of every n-vertex oriented tree with maximum degree Δ(T)⩽cn.
Our first result gives an asymptotic form of a conjecture by Havet and Thomassé, while the second improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree.
| Item Type: | Submitted Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Spanning trees (Graph theory), Directed graphs | |||||||||
| Place of Publication: | Cornell University | |||||||||
| Official Date: | 13 July 2022 | |||||||||
| Dates: |
|
|||||||||
| Number of Pages: | 48 | |||||||||
| Institution: | University of Warwick | |||||||||
| Status: | Not Peer Reviewed | |||||||||
| Publication Status: | Submitted | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
