Directed cycles with zero weight in $\mathbb{Z}_p^k$
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909210596343808 |
|---|---|
| author | Letzter, Shoham Morrison, Natasha |
| author_facet | Letzter, Shoham Morrison, Natasha |
| contents | For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $Γ$ on $f$ vertices and every map $w:E(Γ) \rightarrow A$, there exists a directed cycle $C$ in $Γ$ such that $\sum_{e \in E(C)}w(e) = 0$. The study of $f(A)$ was initiated by Alon and Krivelevich (2021). In this article, we prove that $f(\mathbb{Z}_p^k) = O(pk (\log k)^2)$, where $p$ is prime, with an improved bound of $O(k \log k)$ when $p = 2$. These bounds are tight up to a factor which is polylogarithmic in $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_09033 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Directed cycles with zero weight in $\mathbb{Z}_p^k$ Letzter, Shoham Morrison, Natasha Combinatorics For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $Γ$ on $f$ vertices and every map $w:E(Γ) \rightarrow A$, there exists a directed cycle $C$ in $Γ$ such that $\sum_{e \in E(C)}w(e) = 0$. The study of $f(A)$ was initiated by Alon and Krivelevich (2021). In this article, we prove that $f(\mathbb{Z}_p^k) = O(pk (\log k)^2)$, where $p$ is prime, with an improved bound of $O(k \log k)$ when $p = 2$. These bounds are tight up to a factor which is polylogarithmic in $k$. |
| title | Directed cycles with zero weight in $\mathbb{Z}_p^k$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2306.09033 |