The sum-free process

DOI10.37236/8095MaRDI QIDQ2288178zbMATH OpenOpenAlexFDO

Authors Patrick Bennett

Publication date 17 January 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1502.01644, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p13

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: $Ssubseteqmathbb{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 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.

Review text

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.

Recommendations

• Random sum-free subsets of abelian groups
• scientific article; zbMATH DE number 2095511
• Sum-free sets of integers with a forbidden sum
• Estimates related to sumfree subsets of sets of integers
• scientific article; zbMATH DE number 4183487

Cites work

• A note on the random greedy independent set algorithm
• Dynamic concentration of the triangle-free process
• Large girth approximate Steiner triple systems
• Large triangle packings and Tuza's conjecture in sparse random graphs
• On tail probabilities for martingales
• Random sum-free subsets of abelian groups
• The C_ℓ‐free process
• The diamond-free process
• The early evolution of the \(H\)-free process
• The Final Size of the $C_{\ell}$-free Process
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Triangle-free subgraphs in the triangle-free process
• When does the \(K_{4}\)-free process stop?

Cited in

(3)

• Free Jacobi process
• The C_ℓ‐free process
• Absolutely Summing Processes

This page was built for publication: The sum-free process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288178)