Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and be sufficiently large. If has and is any graph on with at least edges then
where
and similarly for .
Source: erdosproblems.com/808
An accepted solution exists. The statement is false.
Disproved. The status-defining source is Theorem 4 of Alon, Ruzsa and Solymosi [ARS20] (Publ. Mat. 64 (2020), 143--155, refereed): for every there is such that for infinitely many some set of integers carries a graph with at least edges along which sums and products together number at most (the paper's and , loose up to powers of the logarithm, which the strict inequality in absorbs); their Theorem 3 is the explicit case with edges and . The paper's positive result, that a graph with edges on integers has , bounds how far the failure can go. The claim page is Alon, Ruzsa and Solymosi (accepted on the refereed publication and the site's credit).