The average-degree rainbow path conjecture for subgraphs of hypercubes

From papers

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 d5d\ge 5.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.