An asymmetric random Rado theorem for single equations: the 0-statement

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Heidelberg University

Abstract

A famous result of Rado characterizes those integer matrices A which are partition regular, that is, for which any finite coloring of the positive integers gives rise to a monochromatic solution to the equation Ax = 0. Aigner-Horev and Person recently stated a conjecture on the probability threshold for the binomial random set [n]p having the
asymmetric random Rado property: given partition regular matrices A1, … , Ar (for a fixed r ≥ 2), however one r-colors [n]p, there is always a color i ∈ [r] such that there is an i-colored solution to Aix = 0. This generalizes the symmetric case, which was resolved by Rödl and Ruci´nski, and Friedgut, Rödl and Schacht. Aigner-Horev and Person proved the 1-statement of their asymmetric conjecture. In this paper, we resolve the 0-statement in the case where the Aix = 0 correspond to single linear equations. Additionally we close a gap in the original proof of the 0-statement of the (symmetric) random Rado theorem.

Details

Original languageEnglish
JournalRandom Structures and Algorithms
Early online date21 Aug 2021
Publication statusE-pub ahead of print - 21 Aug 2021