In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a quasirandom group is a
group that does not contain a large product-free
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
. Such groups are precisely those without a small non-trivial
irreducible representation
In mathematics, specifically in the representation theory of groups and algebras, an irreducible representation (\rho, V) or irrep of an algebraic structure A is a nonzero representation that has no proper nontrivial subrepresentation (\rho, _W,W ...
. The namesake of these groups stems from their connection to
graph theory:
bipartite
Bipartite may refer to:
* 2 (number)
* Bipartite (theology), a philosophical term describing the human duality of body and soul
* Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
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
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
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