Long rainbow paths in graphs and digraphs

Zoom Link

We study an old question in combinatorial group theory which can be traced back to a problem of Graham from 1971, restated by Erd\H{o}s and Graham in 1980. Given a group $\Gamma$, and some subset $S\subseteq \Gamma$, is it possible to permute $S$ as $s_1,s_2,\ldots, s_d$ so that the partial products $\prod_{1\leq i\leq t} s_i$, $t\in [d]$ are all distinct? Most of the progress towards this problem has been in the case when $\Gamma$ is a cyclic group. We show that for any group $\Gamma$ and any $S\subseteq \Gamma$, there is a permutation of $S$ where all but a vanishing proportion of the partial products are distinct, thereby establishing the first asymptotic version of Graham's conjecture under no restrictions on $\Gamma$ or $S$.
    To do so, we explore a natural connection between Graham's problem and the following very natural question attributed to Schrijver. Given a $d$-regular graph $G$ properly edge-coloured with $d$ colours, is it always possible to find a rainbow path with $d-1$ edges? We settle this question asymptotically by showing one can find a rainbow path of length $d-o(d)$.  A certain natural directed analogue of Schrijver's question gives further implications for Graham's conjecture. 
This is based on joint work with Matija Bucic, Bryce Frederickson, Alp Müyesser and Alexey Pokrovskiy.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.