标题： 通过彩虹路径走向格兰姆重排猜想 显示英文标题

标题： Towards Graham's rearrangement conjecture via rainbow paths

摘要： 我们研究了一个在组合群论中的老问题，这个问题可以追溯到1971年Graham提出的猜想。 给定一个群$\Gamma$，以及某个子集$S\subseteq \Gamma$，是否可以将$S$重新排列为$s_1, s_2, \ldots, s_d$，使得部分乘积$\prod_{1 \leq i \leq t} s_i$，$t\in [d]$都是不同的？ 大多数关于这个问题的进展都是在$\Gamma$是循环群的情况下取得的。 我们证明，对于任何群$\Gamma$和任何$S \subseteq \Gamma$，存在一个$S$的排列，使得几乎所有部分乘积都是不同的，从而在不施加任何关于$\Gamma$或$S$的限制的情况下，确立了格雷厄姆猜想的第一个渐近版本。为了做到这一点，我们探讨了格雷厄姆问题与以下一个自然问题之间的联系，该问题归功于施里弗。 给定一个$d$正则图$G$，用$d$种颜色进行恰当边着色，是否总能找到一条具有$d-1$条边的彩虹路径？ 我们通过证明可以找到长度为$d - o(d)$的彩虹路径来解决这个问题。 虽然这在例如当$\Gamma = \mathbb{F}_2^k$时对格雷厄姆的问题有直接应用，但上述一般结果需要我们获得关于施里杰弗问题自然定向类似问题的更复杂的结果。 显示英文摘要

摘要： We study an old question in combinatorial group theory which can be traced back to a conjecture of Graham from 1971. 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)$. While this has immediate applications to Graham's question for example when $\Gamma = \mathbb{F}_2^k$, our general result above requires a more involved result we obtain for the natural directed analogue of Schrijver's question.