Abstract:It is shown that there exists $c > 0$ so that the Cayley graph over any finite abelian group $Z$ generated by $c \log |Z|$ random elements is properly 3-colorable with high probability (as $|Z| \to \infty$). This is asymptotically tight and improves the best-known bound due to Alon of $\frac{1}{4}\log \log |Z|$ elements. It also makes progress toward Alon's suggestion that a bound of $c \log |G|$ may hold for any finite solvable group $G$.
From: Nathan Tung [view email]
[v1]
Mon, 22 Jun 2026 13:46:32 UTC (21 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。