Lewko's blog

An improved upper bound for the sum-free subset constant

Posted in math.CO, Paper, Uncategorized by Mark Lewko on August 27, 2010

I recently arXiv’ed a short note titled An Improved Upper Bound for the Sum-free Subset Constant. In this post I will briefly describe the result.

We say a set of natural numbers A is sum-free if there is no solution to the equation x+y=z with x,y,z \in A. The following is a well-known theorem of Erdős.

Theorem Let A be a finite set of natural numbers. There exists a sum-free subset S \subseteq A such that |S| \geq \frac{1}{3}|A|.

The proof of this theorem is a common example of the probabilistic method and appears in many textbooks. Alon and Kleitman have observed that Erdős’ argument essentially gives the theorem with the slightly stronger conclusion |S| \geq \frac{|A|+1}{3}. Bourgain  has improved this further, showing that the conclusion can be strengthened to |S| \geq \frac{|A| + 2}{3}. Bourgain’s estimate is sharp for small sets, and improving it for larger sets seems to be a difficult problem. There has also been interest in establishing upper bounds for the problem. It seems likely that the constant 1/3 cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant \frac{1}{3} could not be replaced by a number greater than 3/7 \approx .429 by considering the set \{2,3,4,5,6,8,10\}. In 1990, Alon and Kleitman improved this to 12/29 \approx .414. In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than 4/10 = .4.  While we have not seen Malouf’s proof, we note that this can be established by considering the set \{1,2,3,4,5,6,8,9,10,18\}. In this note we further improve on these results by showing that the optimal constant cannot be greater than 11/28 \approx .393.

Tagged with: ,