Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-04T21:23:07.008Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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