Rainbow Erdős–Sós conjecture for hypercubes

From papers

For a graph GG and a graph FF, let ex(G,F)\mathrm{ex^*}(G,F) be the maximum number of edges in a subgraph of GG that has a proper edge-coloring with no rainbow copy of FF. The nn-dimensional hypercube QnQ_n has vertex set {0,1}n\{0,1\}^n, with two vertices adjacent when they differ in exactly one coordinate. Rainbow Erdős–Sós conjecture for hypercubes. For each nNn\in\mathbb{N},

ex(Qn,T)=ex(Qn,K1,k)\mathrm{ex^*}(Q_n,T)=\mathrm{ex^*}(Q_n,K_{1,k})

for all trees TT on kk edges; equivalently, QnQ_n satisfies the host-graph version of the rainbow Erdős–Sós question. This conjecture proposes that the rainbow extremal number on the hypercube depends only on the number of edges in the forbidden tree. The supplied text gives no resolution.

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, Dylan King and Sam Spiro, “Rainbow Erdős-Sós Conjectures”, arXiv:2502.00135 (2025).

Solutions 0

No solutions have been posted yet.