The sum-free process

Patrick Bennett¹

¹Western Michigan University

The electronic journal of combinatorics, Tome 27 (2020) no. 1

Résumé

$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:=\varnothing$, 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 Bennett and Bohman, and also matches the order of a sharp threshold result proved by Balogh, Morris and Samotij. 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.

Détail

DOI : 10.37236/8095

Classification : 05C65, 05C85, 05C60, 05D40