Problem Statement
Let $c,\epsilon>0$ and $n$ be sufficiently large. If $A\subset \mathbb{N}$ has $\lvert A\rvert=n$ and $G$ is any graph on $A$ with at least $n^{1+c}$ edges then\[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \geq \lvert A\rvert^{1+c-\epsilon},\]where\[A+_GA = \{ a+b : (a,b)\in G\}\]and similarly for $A\cdot_GA$.
Categories:
Additive Combinatorics Graph Theory
Progress
A problem often attributed to Erdős and Szemerédi, which strengthens the conjecture [52], although it appears in [Er77c] without attribution to Szemerédi.This strong conjecture was disproved by Alon, Ruzsa, and Solymosi [ARS20], who constructed (for arbitrarily large $n$) a set of integers $A$ with $\lvert A\rvert=n$ and a graph $G$ with $\gg n^{5/3-o(1)}$ many edges such that\[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \ll \lvert A\rvert^{4/3+o(1)}.\]Alon, Ruzsa, and Solymosi do prove, however, that if $A$ has size $n$ and $G$ has $m$ edges then\[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \gg m^{3/2}n^{-7/4}.\]
Source: erdosproblems.com/808 | Last verified: January 16, 2026