The average-degree rainbow path conjecture for subgraphs of hypercubes

About 1 year old · traced to

Let QnQ_n be the nn-dimensional hypercube, and let GG be a subgraph of QnQ_n. A proper edge-coloring of GG is one in which incident edges receive distinct colors, and a rainbow copy of a graph is a copy whose edges receive pairwise distinct colors.

Average-degree rainbow path conjecture. If GG has average degree at least dd, then every proper edge-coloring of GG contains a rainbow copy of the path on dd edges.

This is an average-degree analogue of the Erdős–Sós conjecture and a rainbow conjecture proposed in the cited work. Even for subgraphs of hypercubes, the assertion remains open for d≥5d\ge 5.

References

Primary source

Nicholas Crawford, Maya Sankar, Carl Schildkraut and Sam Spiro, “Rainbow Trees in Hypercubes”, arXiv:2508.14186 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.