论文标题
随机扰动集的Schur属性
Schur properties of randomly perturbed sets
论文作者
论文摘要
如果任何两种颜色的$ a $结果在单色$ x，y $和$ z $中，$ a $ a $ a $ a $ a $ a $ a $ a $ x+y = z $。我们研究以下问题：需要将多少个从$ [n] $添加到某些$ a \ subseteq [n] $的随机整数，以确保产生的集合是Schur的可能性很高？胡在1980年表明，当$ | a |> \ lceil \ tfrac {4n} {5} \ rceil $时，不需要随机整数，因为$ a $已经保证为schur。最近，Aigner-Horev和人表明，对于任何密集的整数集$ a \ subseteq [n] $，添加$ω（n^{1/3}）$随机整数足够了，请注意，这对于带有$ | a | a | a | a | \ leq \ leq \ lceil \ lceil \ tfrac \ tfrac \ tfrac \ tfrac n n n} $ a $ a $都是最佳的。我们通过证明$ a \ subseteq [n] $带有$ | a | = \ lceil \ tfrac {n} {2} {2} {2} \ rceil+t <\ lceil+tfrac {4n n n} {5} {5} {5} \ rceil $，然后添加$ω（\ min \ {n^{1/3}，nt^{ - 1} \}）$随机整数将在Schur的集合中具有很高的概率结果。我们的结果对于所有$ t $都是最佳的，我们进一步提供了稳定结果，表明当$ a $结构不接近极端示例时，一个人需要的随机整数要少得多。我们还通过使用算法论证和HyperGraph容器的理论来提供非平凡的上限和下限，从而启动了整数$ a $的稀疏集的研究。
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 $A\subseteq [n]$ to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when $|A|> \lceil\tfrac{4n}{5}\rceil$, 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\subseteq [n]$, adding $ω(n^{1/3})$ random integers suffices, noting that this is optimal for sets $A$ with $|A|\leq \lceil\tfrac{n}{2}\rceil$. We close the gap between these two results by showing that if $A\subseteq [n]$ with $|A|=\lceil\tfrac{n}{2}\rceil+t<\lceil\tfrac{4n}{5}\rceil$, then adding $ω(\min\{n^{1/3},nt^{-1}\})$ 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. We also initiate the study of perturbing sparse sets of integers $A$ by using algorithmic arguments and the theory of hypergraph containers to provide nontrivial upper and lower bounds.
