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 configurations.
Chromatic thresholds for linear equations and recurrence
2 Pith papers cite this work. Polarity classification is still indexing.
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.
fields
math.CO 2years
2026 2representative citing papers
citing papers explorer
-
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 configurations.