Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs
Abstract
We study rainbow spanning configurations in bijumbled graphs whose edges are coloured independently and uniformly from a prescribed palette. For n-vertex (p,β)-bijumbled graphs with minimum degree at least a fixed positive multiple of pn, we obtain rainbow perfect matchings and Hamilton cycles with a sufficient palette surplus of order (log n)/p, assuming pn=ω(log n) and β≤ cpn for a sufficiently small constant c. For each prescribed spanning tree of fixed maximum degree Δ≥2, a surplus of order Ln,Δ(log n)/p suffices under β≤ cpn/Ln,Δ, where Ln,Δ=Δ5√(log n). The palette surplus is sublinear under these hypotheses. These results use a McDiarmid-type coupling and retain the discrepancy scales of the relevant deterministic embedding theorems. We also prove exact-palette results, using precisely as many colours as the number of edges of the target configuration. After independent edge percolation at rate ρ, it is shown that a rainbow perfect matching or Hamilton cycle exists asymptotically almost surely when ρpn ≥ C(log n)2 and β≤γpn for appropriate constants C and γ. We obtain corresponding results for each prescribed bounded-degree spanning tree and for clique factors under appropriate stronger hypotheses. The exact-palette proofs construct spread measures from uncoloured containment estimates and apply the rainbow threshold theorem of Han and Yuan.
Related
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
- Resilience of rainbow Hamilton cycles in pseudorandom graphs
- Streaming Hypergraph Coloring via Palette Sparsification
- Exact three-component covers in 2-coloured random bipartite graphs
- Partial Airy ideals and coloured blobbed topological recursion
BibTeX
@misc{aignerhorev2026exactpalette,
title = {{Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs}},
author = {Elad Aigner-Horev and Dan Hefetz and Yury Person and Michael Trushkin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30304},
eprint = {2609.30304},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30304},
}
RIS
TY - UNPB
TI - Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs
AU - Elad Aigner-Horev
AU - Dan Hefetz
AU - Yury Person
AU - Michael Trushkin
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.30304
UR - https://arxiv.org/abs/2609.30304
AB - We study rainbow spanning configurations in bijumbled graphs whose edges are coloured independently and uniformly from a prescribed palette. For n-vertex (p,β)-bijumbled graphs with minimum degree at least a fixed positive multiple of pn, we obtain rainbow perfect matchings and Hamilton cycles with a sufficient palette surplus of order (log n)/p, assuming pn=ω(log n) and β≤ cpn for a sufficiently small constant c. For each prescribed spanning tree of fixed maximum degree Δ≥2, a surplus of order L_n,Δ(log n)/p suffices under β≤ cpn/L_n,Δ, where L_n,Δ=Δ^5√(log n). The palette surplus is sublinear under these hypotheses. These results use a McDiarmid-type coupling and retain the discrepancy scales of the relevant deterministic embedding theorems. We also prove exact-palette results, using precisely as many colours as the number of edges of the target configuration. After independent edge percolation at rate ρ, it is shown that a rainbow perfect matching or Hamilton cycle exists asymptotically almost surely when ρpn ≥ C(log n)^2 and β≤γpn for appropriate constants C and γ. We obtain corresponding results for each prescribed bounded-degree spanning tree and for clique factors under appropriate stronger hypotheses. The exact-palette proofs construct spread measures from uncoloured containment estimates and apply the rainbow threshold theorem of Han and Yuan.
ER -