Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T10:09:48.892Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

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]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