A group with no large product-free subset
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.
 ;templatestyles src="Template:TOC_left/styles.css" / ;
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 formula_1 for which every finite group formula_2 with order formula_3 has a product-free subset with size at least formula_4. A well-known result of Paul Erdős about sum-free sets of integers can be used to prove that formula_5 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 formula_3. A lower bound of formula_7 can be proved by taking a large subset of a union of sufficiently many cosets, and an upper bound of formula_8 is given by considering the projective special linear group formula_9 for any prime formula_10. 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 formula_11 A sequence of bipartite graphs formula_12 (here formula_3 is allowed to skip integers as long as formula_3 tends to infinity) with formula_15 having formula_3 vertices, vertex parts formula_17 and formula_18, and formula_19 edges is quasirandom if any of the following equivalent conditions hold:
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 formula_17 and formula_18 independently with probability formula_50
Though quasirandomness can only be defined for sequences of graphs, a notion of formula_1-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 formula_30 term can be replaced by a small constant formula_53, and any graph satisfying that particular modified condition can be termed formula_1-quasirandom. It turns out that formula_1-quasirandomness under any condition is equivalent to formula_56-quasirandomness under any other condition for some absolute constant formula_57
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 formula_58 and a subset formula_59, the bipartite Cayley graph formula_60 is the bipartite graph with vertex sets formula_26 and formula_28, each labeled by elements of formula_2, whose edges formula_64 are between vertices whose ratio formula_65 is an element of formula_66
Definition.
With the tools defined above, one can now define group quasirandomness. A sequence of groups formula_67 with formula_68 (again, formula_3 is allowed to skip integers) is quasirandom if for every real number formula_70 and choice of subsets formula_71 with formula_72, the sequence of graphs formula_73 is quasirandom.
Though quasirandomness can only be defined for sequences of groups, the concept of formula_1-quasirandomness for specific groups can be extended to groups using the definition of formula_1-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 formula_67, the following are equivalent:
Cayley graphs generated from pseudorandom groups have strong mixing properties; that is, formula_83 is a bipartite formula_84-graph for some formula_85 tending to zero as formula_3 tends to infinity. (Recall that an formula_84 graph is a graph with formula_3 vertices, each with degree formula_89, whose adjacency matrix has a second largest eigenvalue of at most formula_90)
In fact, it can be shown that for any formula_1-quasirandom group formula_58, the number of solutions to formula_93 with formula_94, formula_95, and formula_96 is approximately equal to what one might expect if formula_97 was chosen randomly; that is, approximately equal to formula_98 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;