In mathematics, a quasirandom group is a group that does not contain a large product-free subset. Such groups are precisely those without a small non-trivial irreducible representation. The namesake of these groups stems from their connection to graph theory: bipartite Cayley graphs over any subset of a quasirandom group are always bipartite quasirandom graphs.
Motivation The notion of quasirandom groups arises when considering subsets of groups for which no two elements in the subset have a product in the subset; such subsets are termed product-free. László Babai and Vera Sós asked about the existence of a constant c {\displaystyle c} for which every finite group G {\displaystyle G} with order n {\displaystyle n} has a product-free subset with size at least c n {\displaystyle cn} . A well-known result of Paul Erdős about sum-free sets of integers can be used to prove that c = 1 3 {\textstyle c={\frac {1}{3}}} suffices for abelian groups, but it turns out that such a constant does not exist for non-abelian groups. Both non-trivial lower and upper bounds are now known for the size of the largest product-free subset of a group with order n {\displaystyle n} . A lower bound of c n 11 14 {\textstyle cn^{\frac {11}{14}}} can be proved by taking a large subset of a union of sufficiently many cosets, and an upper bound of c n 8 9 {\textstyle cn^{\frac {8}{9}}} is given by considering the projective special linear group PSL ( 2 , p ) {\displaystyle \operatorname {PSL} (2,p)} for any prime p {\displaystyle p} . In the process of proving the upper bound, Timothy Gowers defined the notion of a quasirandom group to encapsulate the product-free condition and proved equivalences involving quasirandomness in graph theory.
Graph quasirandomness
Formally, it does not make sense to talk about whether or not a single group is quasirandom. The strict definition of quasirandomness will apply to sequences of groups, but first bipartite graph quasirandomness must be defined. The motivation for considering sequences of groups stems from its connections with graphons, which are defined as limits of graphs in a certain sense. Fix a real number p ∈ [ 0 , 1 ] . {\displaystyle p\in [0,1].} A sequence of bipartite graphs ( G n ) {\displaystyle (G_{n})} (here n {\displaystyle n} is allowed to skip integers as long as n {\displaystyle n} tends to infinity) with G n {\displaystyle G_{n}} having n {\displaystyle n} vertices, vertex parts A n {\displaystyle A_{n}} and B n {\displaystyle B_{n}} , and ( p + o ( 1 ) ) | A n | | B n | {\displaystyle (p+o(1))|A_{n}||B_{n}|} edges is quasirandom if any of the following equivalent conditions hold:
For every bipartite graph H {\displaystyle H} with vertex parts A ′ {\displaystyle A'} and B ′ {\displaystyle B'} , the number of labeled copies of H {\displaystyle H} in G n {\displaystyle G_{n}} with A ′ {\displaystyle A'} embedded in A {\displaystyle A} and B ′ {\displaystyle B'} embedded in B {\displaystyle B} is ( p e ( H ) + o ( 1 ) ) | A | | A ′ | | B | | B ′ | . {\textstyle \left(p^{e(H)}+o(1)\right)|A|^{|A'|}|B|^{|B'|}.} Here, the function o ( 1 ) {\displaystyle o(1)} is allowed to depend on H . {\displaystyle H.}
… excerpt ends here. Continue reading the full article.
