Chromatic thresholds for linear equations and recurrence
read the original abstract
Motivated by classical problems in extremal graph theory, we study a chromatic analogue of Roth-type questions for linear equations over $\mathbb F_p$. Given a homogeneous equation $\mathcal L:\sum_{i=1}^k c_i x_i=0$ with $k\ge 3$, we study $\mathcal L$-solution-free sets $A\subseteq \mathbb F_p$ through the chromatic number of the Cayley graph $\mathsf{Cay}(\mathbb F_p,A)$. We introduce the \emph{chromatic threshold} $\delta_\chi(\mathcal L)$, the minimum density that guarantees bounded chromatic number of $\mathsf{Cay}(\mathbb F_p,A)$ among all $\mathcal L$-solution-free sets $A$, and determine exactly when $\delta_\chi(\mathcal L)=0$. We prove that $\delta_\chi(\mathcal L)=0$ if and only if $\mathcal L$ contains a zero-sum subcollection of at least three coefficients. A key ingredient is a quantitative chromatic lower bound for Cayley graphs on $\mathbb Z_p^n$ generated by Hamming balls around the all-ones vector. This is obtained by introducing a new Kneser-type graph that admits a natural embedding into $\mathbb Z_p^n$, together with an equivariant Borsuk--Ulam type argument. As a consequence, we resolve a question of Griesmer. We further relate our classification to the hierarchy of measurable, topological, and Bohr recurrence. In particular, we show that every infinite discrete abelian group admits a set that is topological recurrent but not measurable recurrent, extending the seminal examples of K\v{r}\'i\v{z} and Ruzsa.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Chromatic thresholds for pairs of graphs
For pairs of 3-chromatic graphs H1 and H2, the two-color Ramsey chromatic threshold is exactly one of 2/3, 5/7, 3/4, 7/9, or 4/5, determined by the individual chromatic thresholds and embeddability into C5-type Ramsey...
-
Linear equations and chromatic thresholds in $B_h$ sets
Derives size bounds and pseudorandomness for equation-avoiding B_h sets, plus chromatic threshold results for Sidon sets.
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.