Spring 2017

A Solution to the Burr-Erdos Problems on Ramsey Completeness

Thursday, Jun. 21, 2018 11:15 am12:00 pm

Add to Calendar

A sequence A of positive integers is r-Ramsey complete if for every r-coloring of A, every sufficiently large integer can be written as a sum of the elements of a monochromatic subsequence. Burr and Erdos proposed several open problems on how sparse can an r-Ramsey complete sequence be and which polynomial sequences are r-Ramsey complete. Erdos later offered cash prizes for two of these problems. We prove a result which solves the problems of Burr and Erdos on Ramsey complete sequences. The proofs use randomness and expansion ideas related to pseudorandomness. Joint work with David Conlon.