Sums and products along sparse graphs |
| |
| Authors: | Noga Alon Omer Angel Itai Benjamini Eyal Lubetzky |
| |
| Institution: | 1.Sackler School of Mathematics and Blavatnik School of Computer Science,Tel Aviv University,Tel Aviv,Israel;2.Microsoft-Israel R&D Center,Herzeliya,Israel;3.Department of Mathematics,University of British Columbia,Vancouver,Canada;4.Department of Mathematics,The Weizmann Institute of Science,Rehovot,Israel;5.Microsoft Research,One Microsoft Way,Redmond,USA |
| |
| Abstract: | In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n
1+ɛ
distinct sums of pairs or that many distinct products, and conjectured a lower bound of n
2−o(1). They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given
graph G on n labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least n
1+ɛ
edges. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
