Sums, products, and ratios along the edges of a graph (Q2302174): Difference between revisions

\textit{P. Erdős} and \textit{E. Szemerédi} [Stud. Pure Math. Mem. P. Turán, 213--218 (1983; Zbl 0526.10011)] proved that every finite set of integers \(\mathcal{A}\) of sufficiently large cardinality satisfies \(\max(|\mathcal{A}+\mathcal{A}|, |\mathcal{A}\mathcal{A}|)=\Omega(|\mathcal{A}|^{1+\delta})\) for some \(\delta>0\) and conjectured that \(\max(|\mathcal{A}+\mathcal{A}|, |\mathcal{A}\mathcal{A}|)\geq|\mathcal{A}|^{2-\varepsilon}\) where \(\varepsilon\to0\) as \(\mathcal{A}\to\infty\). They formulated a stronger conjecture: Let \(G(n,k)\) be a graph of \(n\) vertices \(x_1,x_2,\dots,x_n\) and \(k\) edges. Let a real number \(a_i\) is assigned to \(x_i\), \(i=1,2,\dots,n\). They conjectured that for every \(\varepsilon>0\) and \(0<\alpha\leq 1\) if \(k>n^{1+\alpha}\) there are more than \(n^{1+\alpha-\varepsilon}\) distinct integers of the form \(\{a_i+a_j, a_i,a_j\}\) provided \(x_i\) is joined to \(x_j\). The authors show that this strong form of the Erdős-Szemerédi conjecture does not hold. They also give upper and lower estimates on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.