Quasirandom group
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  for which every finite group  with order  has a product-free subset with size at least . A well-known result of Paul Erdős about sum-free sets of integers can be used to prove that  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 . A lower bound of  can be proved by taking a large subset of a union of sufficiently many cosets, and an upper bound of  is given by considering the projective special linear group  for any prime . 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  A sequence of bipartite graphs  (here  is allowed to skip integers as long as  tends to infinity) with  having  vertices, vertex parts  and , and  edges is quasirandom if any of the following equivalent conditions hold:

 For every bipartite graph  with vertex parts  and , the number of labeled copies of  in  with  embedded in  and  embedded in  is  Here, the function  is allowed to depend on 
 The number of  closed, labeled walks of length 4 in  starting in  is 
 The number of edges between  and  is  for any pair of subsets  and 
 , where  denotes the number of common  neighbors of  and 
 
 The largest eigenvalue of 's adjacency matrix is  and all other eigenvalues have magnitude at most 

It is a result of Chung–Graham–Wilson that each of the above conditions is equivalent. Such graphs are termed quasirandom because each condition asserts that the quantity being considered is approximately what one would expect if the bipartite graph was generated according to the  Erdős–Rényi random graph model; that is, generated by including each possible edge between  and  independently with probability 

Though quasirandomness can only be defined for sequences of graphs, a notion of -quasirandomness can be defined for a specific graph by allowing an error tolerance in any of the above definitions of graph quasirandomness. To be specific, given any of the equivalent definitions of quasirandomness, the  term can be replaced by a small constant , and any graph satisfying that particular modified condition can be termed -quasirandom. It turns out that -quasirandomness under any condition is equivalent to -quasirandomness under any other condition for some absolute constant 

The next step for defining group quasirandomness is the Cayley graph. Bipartite Cayley graphs give a way from translating quasirandomness in the graph-theoretic setting to the group-theoretic setting. Given a finite group  and a subset , the bipartite Cayley graph  is the bipartite graph with vertex sets  and , each labeled by elements of , whose edges  are between vertices whose ratio  is an element of

Definition 

With the tools defined above, one can now define group quasirandomness. A sequence of groups  with  (again,  is allowed to skip integers) is quasirandom if for every real number  and choice of subsets  with , the sequence of graphs  is quasirandom. Though quasirandomness can only be defined for sequences of groups, the concept of -quasirandomness for specific groups can be extended to groups using the definition of -quasirandomness for specific graphs. Properties 

As proved by Gowers, group quasirandomness turns out to be equivalent to a number of different conditions. To be precise, given a sequence of groups , the following are equivalent:

  is quasirandom; that is, all sequences of Cayley graphs defined by  are quasirandom. The dimension of the smallest non-trivial representation of  is unbounded. The size of the largest product-free subset of  is 
 The size of the smallest non-trivial  quotient of  is unbounded. Cayley graphs generated from pseudorandom groups have  strong mixing properties; that is,  is a bipartite -graph for some  tending to zero as  tends to infinity. (Recall that an  graph is a graph with  vertices, each with degree , whose adjacency matrix has a second largest eigenvalue of at most )

In fact, it can be shown that for any -quasirandom group , the number of solutions to  with , , and  is approximately equal to what one might expect if  was chosen randomly; that is, approximately equal to  This result follows from a direct application of the expander mixing lemma. Examples 

There are several notable families of quasirandom groups. In each case, the quasirandomness properties are most easily verified by checking the dimension of its smallest non-trivial representation. The projective special linear groups  for prime  form a sequence of quasirandom groups, since a classic result of Frobenius states that its smallest non-trivial representation has dimension at least  In fact, these groups are the groups with the largest known minimal non-trivial representation, as a function of group order. The alternating groups  are quasirandom, since its smallest non-trivial representation has dimension 
 Any sequence of non-cyclic simple groups with increasing order is quasirandom, since its smallest non-trivial representation has dimension at least , where  is the order of the group. References

Graph theory
Group theory