Sparse Roth-type results hold in near-maximal B_h sets; Sidon sets free of equations with five-coefficient zero-sums are small or have bounded-chromatic Cayley graphs, with constructions for the four-coefficient case.
Coloring sparse random Cayley graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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$.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Linear equations and chromatic thresholds in $B_h$ sets
Sparse Roth-type results hold in near-maximal B_h sets; Sidon sets free of equations with five-coefficient zero-sums are small or have bounded-chromatic Cayley graphs, with constructions for the four-coefficient case.