Sums, products, and ratios along the edges of a graph

Noga Alon; Imre Ruzsa; József Solymosi

doi:10.5565/PUBLMAT6412006

Sums, products, and ratios along the edges of a graph

Noga Alon, Imre Ruzsa, József Solymosi

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

In their seminal paper Erdos and Szemerédi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdos–Szemerédi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.

Original language	English (US)
Pages (from-to)	143-155
Number of pages	13
Journal	Publicacions Matematiques
Volume	64
Issue number	1
DOIs	https://doi.org/10.5565/PUBLMAT6412006
State	Published - 2020

All Science Journal Classification (ASJC) codes

Mathematics(all)

Keywords

Incidence geometry
Sum-product problems
Sumset

Access to Document

10.5565/PUBLMAT6412006

Cite this

@article{8cbf429596474db6aeaefaf26e44720f,

title = "Sums, products, and ratios along the edges of a graph",

abstract = "In their seminal paper Erdos and Szemer{\'e}di formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdos–Szemer{\'e}di conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.",

keywords = "Incidence geometry, Sum-product problems, Sumset",

author = "Noga Alon and Imre Ruzsa and J{\'o}zsef Solymosi",

note = "Funding Information: The first named author is supported in part by NSF grant DMS-1855464, ISF grant 281/17, and the Simons Foundation. The second named author is supported in part by an OTKA NK 104183 grant. The third named author is supported in part by a NSERC and an OTKA NK 104183 grant. Publisher Copyright: {\textcopyright} 2020 Universitat Autonoma de Barcelona. All rights reserved.",

year = "2020",

doi = "10.5565/PUBLMAT6412006",

language = "English (US)",

volume = "64",

pages = "143--155",

journal = "Publicacions Matematiques",

issn = "0214-1493",

publisher = "Universitat Autonoma de Barcelona, Seccio de Matematiques",

number = "1",

}

TY - JOUR

T1 - Sums, products, and ratios along the edges of a graph

AU - Alon, Noga

AU - Ruzsa, Imre

AU - Solymosi, József

N1 - Funding Information: The first named author is supported in part by NSF grant DMS-1855464, ISF grant 281/17, and the Simons Foundation. The second named author is supported in part by an OTKA NK 104183 grant. The third named author is supported in part by a NSERC and an OTKA NK 104183 grant. Publisher Copyright: © 2020 Universitat Autonoma de Barcelona. All rights reserved.

PY - 2020

Y1 - 2020

N2 - In their seminal paper Erdos and Szemerédi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdos–Szemerédi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.

AB - In their seminal paper Erdos and Szemerédi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdos–Szemerédi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.

KW - Incidence geometry

KW - Sum-product problems

KW - Sumset

UR - http://www.scopus.com/inward/record.url?scp=85078715084&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078715084&partnerID=8YFLogxK

U2 - 10.5565/PUBLMAT6412006

DO - 10.5565/PUBLMAT6412006

M3 - Article

AN - SCOPUS:85078715084

SN - 0214-1493

VL - 64

SP - 143

EP - 155

JO - Publicacions Matematiques

JF - Publicacions Matematiques

IS - 1

ER -

Sums, products, and ratios along the edges of a graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this