Sums, products, and ratios along the edges of a graph
\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.
- scientific article; zbMATH DE number 953250
- On multiple sum and product sets of finite sets of integers.
- Proof of the Erdős matching conjecture in a new range
- scientific article; zbMATH DE number 3330856
- On prime factors of sums of integers III
- The dimension of sums of graphs
- scientific article; zbMATH DE number 36206
- Sums and products along sparse graphs
- Bipartite subgraphs
- On sets free of sumsets with summands of prescribed size
- The multiplication table problem for bipartite graphs
- Sums and products along sparse graphs
- The Elekes-Szabó problem and the uniformity conjecture
- Constructions for the Elekes-Szabó and Elekes-Rónyai problems
- Improved bounds for pencils of lines
- Sums, products, and dilates on sparse graphs
- On sums and products along the edges, II
This page was built for publication: Sums, products, and ratios along the edges of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302174)
