Richard P. Stanley Seminar in Combinatorics: Approximate versions of Graham’s conjecture

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? Prior to our work, 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$.Graham’s rearrangement conjecture has a natural translation to a graph theoretic question, and that is the setup we use to prove our results. Given a subset $S$ of a group $\Gamma$, we define the \emph{colored directed Cayley graph} on $\Gamma$ with \emph{generator set} $S$ to be the edge-colored directed graph $\mathrm{Cay}(\Gamma,S)$ on the vertex set $\Gamma$ with an edge from $a$ to $ag$ of color $g$ for every $a \in \Gamma$ and $g \in S$. It is not hard to see that the set $S$ is rearrangeable if and only if the Cayley graph $\mathrm{Cay}(\Gamma,S)$ has a directed path of length $|S|-1$. For undirected graphs, we showed that any properly edge-colored $d$-regular graph contains a rainbow path of length $(1-o(1))d$ solving a conjecture of Schrijver, asymptotically. For directed graphs, we could only get a rainbow directed path of length $d-o(d)$ in the dense regime when $d=\Omega(|G|)$.

This is joint work with Matija Bucić, Bryce Frederickson, Alp Müyesser and Alexey Pokrovskiy.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/