Premium
Tight bounds on additive Ramsey‐type numbers
Author(s) -
Cwalina Karol,
Schoen Tomasz
Publication year - 2017
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms.12081
Subject(s) - combinatorics , mathematics , upper and lower bounds , natural number , van der waerden's theorem , integer (computer science) , constant (computer programming) , invariant (physics) , mathematical analysis , mathematical physics , computer science , programming language
A classic result of Rado states that for every homogenous regular equation with integer coefficients there is the least natural number R ( n ) such that if the elements of [ N ] = { 1 , … , N } are colored into n colors for N ⩾ R ( n ) , then there is a monochromatic solution to the equation. While density results provide quite accurate bounds for R ( n ) in case of invariant equations, the general upper bounds known have been tower‐like in nature. In this paper we prove that R ( n ) = exp ( O ( n 4 log 4 n ) ) for all homogenous regular equations. Also, we prove that the Schur‐like numbers for the equationx 1 + x 2 + x 3 = y 1 + y 2are at most O ( n − c ( log n / log log n ) n ! ) , for some absolute constant c > 0 . This beats a bound following from a classical Schur's argument. In the last section we establish a new upper bound for the van der Waerden numbers W ( 3 , k ) .