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

Robert Hancock, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

3 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)529-550
Number of pages22
JournalRandom Structures and Algorithms
Volume60
Issue number4
Early online date21 Aug 2021
DOIs
Publication statusPublished - 12 May 2022

Bibliographical note

Funding Information:
The authors are grateful to the Midlands Arts Centre for providing a nice working environment for undertaking this research, and to the two referees for their helpful and careful reviews. This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 648509) and from the MUNI Award in Science and Humanities of the Grant Agency of Masaryk University. This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains.

Publisher Copyright:
© 2021 Wiley Periodicals LLC.

Keywords

  • Rado's theorem
  • arithmetic Ramsey theory
  • random sets of integers
  • Software
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics
  • General Mathematics

ASJC Scopus subject areas

  • Software
  • Applied Mathematics
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'An asymmetric random Rado theorem for single equations: the 0-statement'. Together they form a unique fingerprint.

Cite this