Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-06T09:24:27.566Z Has data issue: false hasContentIssue false
  • English
  • Français

Plünnecke's Inequality

Published online by Cambridge University Press:  05 October 2011

GIORGIS PETRIDIS
GIORGIS PETRIDIS*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: giorgis@cantab.net)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Plünnecke's inequality is a standard tool for obtaining estimates on the cardinality of sumsets and has many applications in additive combinatorics. We present a new proof. The main novelty is that the proof is completed with no reference to Menger's theorem or Cartesian products of graphs. We also investigate the sharpness of the inequality and show that it can be sharp for arbitrarily long, but not for infinite commutative graphs. A key step in our investigation is the construction of arbitrarily long regular commutative graphs. Lastly we prove a necessary condition for the inequality to be attained.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 6 , November 2011 , pp. 921 - 938
Copyright
Copyright © Cambridge University Press 2011

References

[1]Hall, P. (1935) On representatives of subsets. J. London Math. Soc. 10 26–30.CrossRefGoogle Scholar
[2]Malouf, J. L. (1995) On a theorem of Plünnecke concerning the sum of a basis and a set of positive density. J. Number Theory 54 12–22.CrossRefGoogle Scholar
[3]Menger, K. (1927) Zur allgemeinen Kurventheorie. Fund. Math. 10 96–115.CrossRefGoogle Scholar
[4]Nathanson, M. B. (1996) Additive Number Theory: Inverse Problems and the Geometry of Subsets, Springer.CrossRefGoogle Scholar
[5]Plünnecke, H. (1970) Eine zahlentheoretische Anwendung der Graphtheorie. J. Reine Angew. Math. 243 171–183.Google Scholar
[6]Ruzsa, I. Z. (1989) An application of graph theory to additive number theory. Scientia Ser. A 3 97–109.Google Scholar
[7]Ruzsa, I. Z. (1990/1991) Addendum to: An application of graph theory to additive number theory. Scientia Ser. A 4 93–94.Google Scholar
[8]Ruzsa, I. Z. (2009) Sumsets and structure. In Combinatorial Number Theory and Additive Group Theory, Springer.Google Scholar
[9]Tao, T. Additive combinatorics. Lecture notes 1, available online at www.math.ucla.edu/~tao/254a.1.03w.Google Scholar
[10]Tao, T. and Vu, V. H. (2006) Additive Combinatorics, Cambridge University Press.CrossRefGoogle Scholar