Schur's Theorem for randomly perturbed sets
Time:
Venue/Location: Online
Speaker: Shagnik Das (National Taiwan University, Taiwan)
Content:A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We study the following problem: how many random integers from [n] need to be added to some subset A of [n] to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when |A|> 4n/5, no random integers are needed, as A is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers A, adding ω(n^{1/3}) random integers suffices, noting that this is optimal for sets A with |A| < n/2. We close the gap between these two results by showing that if |A| = n/2 + t < 4n/5, then adding ω( min (n^{1/3} , n/t) ) random integers will with high probability result in a set that is Schur. Our result is optimal for all t, and we further provide a stability result showing that one needs far fewer random integers when A is not close in structure to the extremal examples. Finally, we initiate the study of perturbing sparse sets of integers by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.
This is joint work with Charlotte Knierem (ETH Zurich) and Patrick Morris (FU Berlin).
Website Seminar: https://sites.google.com/