Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-11T00:09:35.635Z Has data issue: false hasContentIssue false
  • English
  • Français

Quasirandom Groups

Published online by Cambridge University Press:  01 May 2008

W. T. GOWERS
W. T. GOWERS*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: w.t.gowers@dpmms.cam.ac.uk)
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.

Babai and Sós have asked whether there exists a constant c > 0 such that every finite group G has a product-free subset of size at least c|G|: that is, a subset X that does not contain three elements x, y and z with xy = z. In this paper we show that the answer is no. Moreover, we give a simple sufficient condition for a group not to have any large product-free subset.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 3 , May 2008 , pp. 363 - 387
Copyright
Copyright © Cambridge University Press 2008

References

[1]Babai, L. and Rónyai, L. (1990) Computing irreducible representations of finite groups Math. Comp. 55 705–722.CrossRefGoogle Scholar
[2]Babai, L. and Sós, V. (1985) Sidon sets in groups and induced subgraphs of Cayley graphs. Europ. J. Combin. 6 101–114.CrossRefGoogle Scholar
[3]Bollobás, B. and Nikiforov, V. (2004) Hermitian matrices and graphs: Singular values and discrepancy. Discrete Math. 285 17–32.CrossRefGoogle Scholar
[4]Bourgain, J. and Gamburd, A. Uniform expansion bounds for Cayley graphs of SL2(F p). Preprint.Google Scholar
[5]Chung, F. R. K. and Graham, R. L. (1992) Quasi-random subsets of ℤn. J. Combin. Theory Ser. A 61 64–86.CrossRefGoogle Scholar
[6]Chung, F. R. K., Graham, R. L. and Wilson, R. M. (1989) Quasi-random graphs. Combinatorica 9 345–362.CrossRefGoogle Scholar
[7]Davidoff, G., Sarnak, P. and Valette, A. (2003) Elementary Number Theory, Group Theory, and Ramanujan Graphs, Vol. 55 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge.Google Scholar
[8]Gowers, W. T. (2001) A new proof of Szemerédi's theorem. Geom. Funct. Anal. 11 465–588.CrossRefGoogle Scholar
[9]Gowers, W. T. (2006) Quasirandomness, counting and regularity for 3-uniform hypergraphs. Combin. Probab. Comput. 15 143–184.CrossRefGoogle Scholar
[10]Isaacs, I. M. (2006) Character Theory of Finite Groups, AMS Chelsea Publishing, Providence, RI (corrected reprint of 1976 original).Google Scholar
[11]Kedlaya, K. S. (1997) Large product-free subsets of finite groups. J. Combin. Theory Ser. A 77 339–343.CrossRefGoogle Scholar
[12]Kedlaya, K. S. (1998) Product-free subsets of groups. Amer. Math. Monthly 105 900–906.CrossRefGoogle Scholar
[13]Kedlaya, K. S. Product-free subsets of groups, then and now. Preprint: arXiv:0708.2295v1.Google Scholar
[14]Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–277.Google Scholar
[15]Nikolov, N. and Pyber, L. Product decompositions of quasirandom groups and a Jordan type theorem. Preprint: arXiv:math/0703343v3.Google Scholar
[16]Sarnak, P. and Xue, X. (1991) Bounds for multiplicities of automorphic representations. Duke Math. J. 64 207–227.CrossRefGoogle Scholar
[17]Thomason, A. G. (1987) Pseudo-random graphs. In Proc. Random Graphs: Poznán 1985 (Karonski, M., ed.), Ann. Discrete Math. 33 307–331.Google Scholar