A sparse canonical Rado theorem
math.CO
Submitted: 2026-10-27
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: Canonical Ramsey theory studies structured colour patterns in colourings with arbitrarily many colours.
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 at least3 columns, and every prescribed partition witnessing the columns condition, if p at least Cn-1/m(A), then with probability at least 1-e-cnp every colouring of [n] p contains Ω (p k n k- (A)) canonical solutions of A 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.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality