Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
Abstract
We compare transversal and pattern thresholds for two spanning structures. For every fixed k≥ 3 and α>0, we prove that every sufficiently large n-vertex k-graph collection with minimum codegree at least (1/2+α)n contains a tight Hamilton cycle with any prescribed color pattern. Hence the transversal and pattern thresholds for tight Hamilton cycles coincide asymptotically. For spanning trees, we show that for every α>0 there exists c=c(α)>0 such that every n-vertex graph collection with minimum degree at least (1/2+α)n contains every n-vertex tree with maximum degree at most nc and any prescribed color pattern. On the other hand, we construct spanning trees of maximum degree √n+1 whose pattern threshold exceeds their transversal threshold by a positive linear term.
Related
- Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
- On Hamilton cycles in quasiprimitive graphs of order 2pq
- Alternating Hamilton Paths and Cycles in Poset Products
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Tournaments with many Hamilton cycles
BibTeX
@misc{deng2026prescribed,
title = {{Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees}},
author = {Lirong Deng},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07421},
eprint = {2611.07421},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07421},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
AU - Lirong Deng
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07421
UR - https://arxiv.org/abs/2611.07421
AB - We compare transversal and pattern thresholds for two spanning structures. For every fixed k≥ 3 and α>0, we prove that every sufficiently large n-vertex k-graph collection with minimum codegree at least (1/2+α)n contains a tight Hamilton cycle with any prescribed color pattern. Hence the transversal and pattern thresholds for tight Hamilton cycles coincide asymptotically. For spanning trees, we show that for every α>0 there exists c=c(α)>0 such that every n-vertex graph collection with minimum degree at least (1/2+α)n contains every n-vertex tree with maximum degree at most n^c and any prescribed color pattern. On the other hand, we construct spanning trees of maximum degree √n+1 whose pattern threshold exceeds their transversal threshold by a positive linear term.
ER -