Logo
All Random Solved Random Open
SOLVED
Is it true that, for all sufficiently large $n$, if $G$ is a triangle-free graph on $\{1,\ldots,n\}$ then there must exist three independent points $a,b,a+b$?
A problem of Erdős and Hajnal. Hajnal thought that there is in fact an independent set which is a Hindman set - that is, an independent set of the shape \[\left\{ \sum_{i\in S}a_i : S\subseteq \{1,\ldots,k\}\right\}\] for some $a_1,\ldots,a_k$ (provided $n$ is sufficiently large depending on $k$).

The stated problem has been resolved by Barber (personal communication) who verified using a SAT solver that this is true for all $n\geq 18$. The general question of an independent Hindman set remains open.

Additional thanks to: Ben Barber