Rainbow Erdős-Sós Conjectures

Abstract

An edge colored graph is said to contain rainbow-$F$ if $F$ is a subgraph and every edge receives a different color. In 2007, Keevash, Mubayi, Sudakov, and Verstraëte introduced the \emph{rainbow extremal number} ${\mathrm{ex}}^{\ast }(n,F)$, a variant on the classical Turán problem, asking for the maximum number of edges in a $n$-vertex properly edge-colored graph which does not contain a rainbow-$F$. In the following years many authors have studied the asymptotic behavior of ${\mathrm{ex}}^{\ast }(n,F)$ when $F$ is bipartite. In the particular case that $F$ is a tree $T$, the infamous Erdös-Sós conjecture says that the extremal number of $T$ depends only on the size of $T$ and not its structure. After observing that such a pattern cannot hold for ${\mathrm{ex}}^{\ast }$ in the usual setting, we propose that the relative rainbow extremal number ${\mathrm{ex}}^{\ast }(Q_n,T)$ in the $n$-dimensional hypercube $Q_n$ will satisfy an Erdös-Sós type Conjecture and verify it for some infinite families of trees $T$.

14 pages, 8 figures