Report
Zero sum cycles in complete digraphs
| العنوان: | Zero sum cycles in complete digraphs |
|---|---|
| المؤلفون: | Mészáros, Tamás, Steiner, Raphael |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C20, 05C22, 05C25, 05C38, 05C83, 05E15 |
| الوصف: | Given a non-trivial finite Abelian group $(A,+)$, let $n(A) \ge 2$ be the smallest integer such that for every labelling of the arcs of the bidirected complete graph of order $n(A)$ with elements from $A$ there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining $n(\mathbb{Z}_q)$ for integers $q \ge 2$ was recently considered by Alon and Krivelevich, who proved that $n(\mathbb{Z}_q)=O(q \log q)$. Here we improve their bound and show that $n(\mathbb{Z}_q)$ grows linearly. More generally we prove that for every finite Abelian group $A$ we have $n(A) \le 8|A|$, while if $|A|$ is prime then $n(A) \le \frac{3}{2}|A|$. As a corollary we also obtain that every $K_{16q}$-minor contains a cycle of length divisible by $q$ for every integer $q \ge 2$, which improves a result by Alon and Krivelevich. Comment: 8 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2103.04359 |
| رقم الانضمام: | edsarx.2103.04359 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |