Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T05:18:59.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Difference Covers

Published online by Cambridge University Press:  01 September 2007

TOMASZ SCHOEN
TOMASZ SCHOEN*
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznań, Poland (e-mail: schoen@amu.edu.pl)
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.

Let S be a finite set of integers. We consider a problem of finding D(S), the minimum size of a set A, such that S⊆ A−A. We give a characterization for ‘extremal’ sets and prove lower and upper bounds on D(S) in terms of additive properties of S.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 5 , September 2007 , pp. 775 - 787
Copyright
Copyright © Cambridge University Press 2007

References

[1]Alon, N. and Spencer, J. (2000) The Probabilistic Method, Wiley-Interscience, New York.CrossRefGoogle Scholar
[2]Balog, A. and Szemerédi, E. (1994) A statistical theorem of set addition. Combinatorica 14 263–268.CrossRefGoogle Scholar
[3]Bollobás, B. (1978) Extremal Graph Theory, Academic Press, London.Google Scholar
[4]Colbourn, C. J. and Ling, A. C. H. (2000) Quorums from difference covers. Inform. Processing Letters 75 57–59.CrossRefGoogle Scholar
[5]Freiman, G. (1973) Foundations of a Structural Theory of Set Addition, Vol. 37 of Translations of Math. Monographs, AMS, Providence, RI.Google Scholar
[6]Gowers, W. T. (2001) A new proof of Szemerédi's theorem. Geom. Funct. Anal. 11 465–588.CrossRefGoogle Scholar
[7]Hennecart, F., Robert, G. and Yudin, A. (1999) On the number of sums and differences. Astérisque 258 173–178.Google Scholar
[8]Redei, L. and Rényi, A. (1949) Uber die Darstellung der Zahlen 1,2,¨,N mittels Differenzen. (In Russian.) Mat. Sb., N. Ser. 24 385–389.Google Scholar
[9]Ruzsa, I. Z. (1978) On the cardinality of A±A and A−A. In Combinatorics: Proc. Fifth Hungarian Colloq., Keszthely 1976, Vol. 18 of Coll. Math. Soc. Bolyai, North-Holland, pp. 933–938.Google Scholar