Given an abelian group $G$ of order $n$, how I do show that the number of sum free subsets of G is at most $2^{(n/2 + o(n))}$. Sum free subsets meaning $A\subseteq G$ s.t. $\forall x,y,z \in A, x + y \neq z$ I believe there is a proof by Alon but I do not understand it.
EDIT: The link to Alon's proof is here: https://link.springer.com/content/pdf/10.1007%2FBF02772952.pdf
I particularly don't understand:
1.) Given the Cayley Graph on group G with respect to S $H(G,S)$, I do not see how it is a regular graph and
2.) He says $\sum_{i=1}^{\log(n)} \binom{n}{i} = 2^{o(n)}$, and the number of sum free subsets of cardinality greater than log(n) by theorem 1.2 is at most $2^{(1+o(\log(n)^{-0.1})n/2}$ so is $2^{(1+o(\log(n)^{-0.1})n/2} + 2^{o(n)} \equiv 2^{(1+o(1))n/2}$ ?
3.) I am not understanding the argument of taking S = first log(n) elements of sum free subset A and how that gives us the desired result.
Any help would be appreciated.

  • $\begingroup$ If you want proof-explanation for Alon's approach, you should include it in the post and point out which part got you stuck. $\endgroup$ – Lee David Chung Lin Apr 21 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.