Rainbow Trees in Hypercubes

2025/08/19 by Nicholas Crawford, Crawford, Nicholas, Maya Sankar +5 · 1 citation
Computer Science · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2508.14186

openalex publication_date 2025/08/19 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28

Abstract

We prove that every proper edge-coloring of the n-dimensional hypercube Q_n contains a rainbow copy of every tree T on at most n edges. This result is best possible, as Q_n can be properly edge-colored using only n colors while avoiding rainbow cycles.

Citations

• Towards Graham's rearrangement conjecture via rainbow paths
• A proof of the Ryser-Brualdi-Stein conjecture for large even n
• Essentially tight bounds for rainbow cycles in proper edge-colourings
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• New bounds for Ryser's conjecture and related problems
• Rainbow Turán Problem for Even Cycles

Cited by

• On the Graham--Sloane harmonious labelling conjecture

Related

• Embedding rainbow trees with applications to graph labelling and\n decomposition
• Rainbow Erdős-Sós Conjectures
• Long directed rainbow cycles and rainbow spanning trees
• On Rainbow Cycles and Paths
• Linearly many rainbow trees in properly edge-coloured complete graphs