تقرير
Directed cycles with zero weight in $\mathbb{Z}_p^k$
العنوان: | Directed cycles with zero weight in $\mathbb{Z}_p^k$ |
---|---|
المؤلفون: | Letzter, Shoham, Morrison, Natasha |
سنة النشر: | 2023 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics |
الوصف: | For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $\Gamma$ on $f$ vertices and every map $w:E(\Gamma) \rightarrow A$, there exists a directed cycle $C$ in $\Gamma$ 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$. Comment: 18 pages (including a 3 page appendix) |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2306.09033 |
رقم الأكسشن: | edsarx.2306.09033 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!