The sum-free process (Q2288178): Difference between revisions

Summary: \(S \subseteq \mathbb{Z}_{2n}\) is said to be sum-free if \(S\) has no solution to the equation \(a+b=c\). The sum-free process on \(\mathbb{Z}_{2n}\) starts with \(S:=\emptyset \), and iteratively inserts elements of \(\mathbb{Z}_{2n} \), where each inserted element is chosen uniformly at random from the set of all elements that could be inserted while maintaining that \(S\) is sum-free. We prove a lower bound (which holds with high probability) on the final size of \(S\), which matches a more general result of \textit{P. Bennett} and \textit{T. Bohman} [Random Struct. Algorithms 49, No. 3, 479--502 (2016; Zbl 1349.05314)], and also matches the order of a sharp threshold result proved by \textit{J. Balogh} et al. [Isr. J. Math. 199, Part B, 651--685 (2014; Zbl 1370.11040)]. We also show that the set \(S\) produced by the process has a particular non-pseudorandom property, which is in contrast with several known results about the random greedy independent set process on hypergraphs.