The Strong Erdős–Szemerédi conjecture for sums and products along graph edges

Let GnG_n be a graph on nn vertices, and let AR\mathcal{A}\subset\mathbb{R} be an nn-element set. Define the sumset and product set along GnG_n by

A+GnA={ai+aj:(i,j)E(Gn)},\mathcal{A}+_{G_n}\mathcal{A}=\{a_i+a_j:(i,j)\in E(G_n)\},

and

AGnA={aiaj:(i,j)E(Gn)}.\mathcal{A}\cdot_{G_n}\mathcal{A}=\{a_i a_j:(i,j)\in E(G_n)\}.

Strong Erdős–Szemerédi conjecture. For every c>0c>0 and ε>0\varepsilon>0, there is a threshold n0n_0 such that, if nn0n\geq n_0, then for every nn-element set of reals A\mathcal{A} and every graph GnG_n with at least n1+cn^{1+c} edges,

A+GnA+AGnAA1+cε.|\mathcal{A}+_{G_n}\mathcal{A}|+|\mathcal{A}\cdot_{G_n}\mathcal{A}|\geq |\mathcal{A}|^{1+c-\varepsilon}.

This conjecture was refuted by Alon, Ruzsa, and Solymosi, so it is no longer open.

Sources & referencesView supporting material

Primary source

Noga Alon, Imre Ruzsa and Jozsef Solymosi, “On sums and products along the edges, II”, arXiv:2007.12970 (2023).

Additional references

2 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1802.06405.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.