Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

Note on near-spanning balanced antidirected trees missing from regular tournaments

  • Gregory Gutin
  • Yiming Hao
Open at sourcePDFDOICite

Abstract

We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer n, we exhibit a regular vertex-transitive tournament on n vertices and a balanced antidirected caterpillar on n−1 vertices with maximum degree at most (1+o(1))n/log2 n that is not contained in the tournament. The host satisfies the strict k/2 threshold in both the semidegree and pseudo-semidegree settings, where k is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order n−1 of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.

Related

  1. 4-Arc-Pancyclicity of Regular Multipartite Tournaments
    Weihao Xia
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Cycles in Regular Multipartite Tournaments
    Yufei Chang, Zhilan Wang, Shuo Wei +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Balanced Spanning Trees for Triangular Strip Lattices
    Saugat Dhakal, Long Nguyen, Yandi Wu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Nearly Spanning Regular Subgraphs
    Varun Sivashankar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. A sharp upper bound on the number of spanning forests of regular graphs
    T. Wu, S. Lu, X. Dong
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{gutin2026note,
  title = {{Note on near-spanning balanced antidirected trees missing from regular tournaments}},
  author = {Gregory Gutin and Yiming Hao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02390},
  eprint = {2610.02390},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02390},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Note on near-spanning balanced antidirected trees missing from regular tournaments
AU  - Gregory Gutin
AU  - Yiming Hao
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.02390
UR  - https://arxiv.org/abs/2610.02390
AB  - We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer n, we exhibit a regular vertex-transitive tournament on n vertices and a balanced antidirected caterpillar on n−1 vertices with maximum degree at most (1+o(1))n/log_2 n that is not contained in the tournament. The host satisfies the strict k/2 threshold in both the semidegree and pseudo-semidegree settings, where k is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order n−1 of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.
ER  -