Towards Graham's rearrangement conjecture via rainbow paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915816888336384 |
|---|---|
| author | Bucić, Matija Frederickson, Bryce Müyesser, Alp Pokrovskiy, Alexey Yepremyan, Liana |
| author_facet | Bucić, Matija Frederickson, Bryce Müyesser, Alp Pokrovskiy, Alexey Yepremyan, Liana |
| contents | We study an old question in combinatorial group theory which can be traced back to a conjecture of Graham from 1971. Given a group $Γ$, and some subset $S\subseteq Γ$, 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 $Γ$ is a cyclic group. We show that for any group $Γ$ and any $S \subseteq Γ$, 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 $Γ$ 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 $Γ= \mathbb{F}_2^k$, our general result above requires a more involved result we obtain for the natural directed analogue of Schrijver's question. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards Graham's rearrangement conjecture via rainbow paths Bucić, Matija Frederickson, Bryce Müyesser, Alp Pokrovskiy, Alexey Yepremyan, Liana Combinatorics Group Theory Number Theory 05C35, 05D40, 20K01 We study an old question in combinatorial group theory which can be traced back to a conjecture of Graham from 1971. Given a group $Γ$, and some subset $S\subseteq Γ$, 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 $Γ$ is a cyclic group. We show that for any group $Γ$ and any $S \subseteq Γ$, 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 $Γ$ 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 $Γ= \mathbb{F}_2^k$, our general result above requires a more involved result we obtain for the natural directed analogue of Schrijver's question. |
| title | Towards Graham's rearrangement conjecture via rainbow paths |
| topic | Combinatorics Group Theory Number Theory 05C35, 05D40, 20K01 |
| url | https://arxiv.org/abs/2503.01825 |