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

Robert Hancock; Andrew Treglown

doi:10.1002/rsa.21039

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

Robert Hancock, Andrew Treglown

Mathematics

Research output: Contribution to journal › Article › peer-review

40 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 A_ix = 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 A_ix = 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 language	English
Pages (from-to)	529-550
Number of pages	22
Journal	Random Structures and Algorithms
Volume	60
Issue number	4
Early online date	21 Aug 2021
DOIs	https://doi.org/10.1002/rsa.21039
Publication status	Published - 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

Access to Document

10.1002/rsa.21039Licence: None: All rights reserved

HancockR2021Asymmetric
This is the peer reviewed version of the following article: Hancock, R., Treglown, A., An asymmetric random Rado theorem for single equations: The 0-statement, Random Struct. Algorithms. Vol. 60 issue 4 (2022), 529– 550., which has been published in final form at https://doi.org/10.1002/rsa.21039. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions.
Accepted author manuscript, 408 KBLicence: Other (please specify with Rights Statement)

Cite this

@article{1524256295f948e6825ecd6e75a19094,

title = "An asymmetric random Rado theorem for single equations: the 0-statement",

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 theasymmetric 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{\"o}dl and Ruci´nski, and Friedgut, R{\"o}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.",

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

author = "Robert Hancock and Andrew Treglown",

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: {\textcopyright} 2021 Wiley Periodicals LLC.",

year = "2022",

month = may,

day = "12",

doi = "10.1002/rsa.21039",

language = "English",

volume = "60",

pages = "529--550",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "4",

}

TY - JOUR

T1 - An asymmetric random Rado theorem for single equations

T2 - the 0-statement

AU - Hancock, Robert

AU - Treglown, Andrew

N1 - 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.

PY - 2022/5/12

Y1 - 2022/5/12

N2 - 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 theasymmetric 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.

AB - 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 theasymmetric 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.

KW - Rado's theorem

KW - arithmetic Ramsey theory

KW - random sets of integers

KW - Software

KW - Computer Graphics and Computer-Aided Design

KW - Applied Mathematics

KW - General Mathematics

UR - http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418

UR - http://www.scopus.com/inward/record.url?scp=85113136413&partnerID=8YFLogxK

U2 - 10.1002/rsa.21039

DO - 10.1002/rsa.21039

M3 - Article

SN - 1042-9832

VL - 60

SP - 529

EP - 550

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this