A sparse canonical Rado theorem

Source abstract

Canonical Ramsey theory studies structured colour patterns in colourings with arbitrarily many colours. Lefmann's canonical Rado theorem extends the canonical van der Waerden theorem of Erdős and Graham to partition-regular linear systems. Recently, Alvarado, Kohayakawa, Morris, Mota and Ortega proved a sparse canonical van der Waerden theorem for random set $[n]_p$. In this paper, we prove a sparse canonical Rado theorem. For every irredundant partition-regular matrix $A$ of positive rank with $k\ge3$ columns, and every prescribed partition witnessing the columns condition, if $p\ge Cn^{-1/m(A)}$, then with probability at least $1-e^{-cnp}$ every colouring of $[n]_p$ contains $$Ω\big(p^k n^{k-\rank(A)}\big)$$ canonical solutions of $A\mathbf x=0$ with distinct coordinates. A matching 0-statement holds when the prescribed partition has one or at least three blocks; the Schur equation shows that it can fail for two-block patterns. For every prescribed partition, we also establish a robust threshold at the same scale under deletion of a fixed positive proportion of the random set.