Quasirandom group

In mathematics, a quasirandom group is a group that does not contain a large product-free subset.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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 for which every finite group G with order n has a product-free subset with size at least cn .

A well-known result of Paul Erdős about sum-free sets of integers can be used to prove that 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 . A lower bound of cn^{\frac{11}{14}} can be proved by taking a large subset of a union of sufficiently many cosets, and an upper bound of cn^{\frac{8}{9}} is given by considering the projective special linear group \operatorname{PSL}(2, p) for any prime 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.

For every bipartite graph H with vertex parts A' and B' , the number of labeled copies of H in G_n with A' embedded in A and B' embedded in B is \left(p^{e(H)} + o(1)\right) | A | ^ | B | ^ . Here, the function o(1) is allowed to depend on H. The number of closed, labeled walks of length 4 in G_n starting in A_n is (p^4 + o(1))| A_n |^2 | B_n |^2.

The number of edges between A' and B' is p | A' | | B' | + n^2 o(1) for any pair of subsets A' \subseteq A_n and B' \subseteq B_n. \sum\limits_{a_1, a_2 \in A_n} N(a_1, a_2)^2 = (p^4 + o(1)) | A_n |^2 | B_n |^2 , where N(u, v) denotes the number of common neighbors of u and v. \sum\limits_{b_1, b_2 \in B_n} N(b_1, b_2)^2 = (p^4 + o(1)) | A_n |^2 | B_n |^2. The largest eigenvalue of G_n 's adjacency matrix is (p + o(1)) \sqrt and all other eigenvalues have magnitude at most \sqrt o(1).

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 A_n and B_n independently with probability p. Though quasirandomness can only be defined for sequences of graphs, a notion of c -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 o(1) term can be replaced by a small constant c > 0 , and any graph satisfying that particular modified condition can be termed c -quasirandom. It turns out that c -quasirandomness under any condition is equivalent to c^k -quasirandomness under any other condition for some absolute constant k \geq 1.

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 \Gamma and a subset S \subseteq \Gamma , the bipartite Cayley graph \operatorname{BiCay}(\Gamma, S) is the bipartite graph with vertex sets A and B , each labeled by elements of G , whose edges a \sim b are between vertices whose ratio ab^{-1} is an element of S. With the tools defined above, one can now define group quasirandomness. A sequence of groups (\Gamma_n) with | \Gamma_n | = n (again, n is allowed to skip integers) is quasirandom if for every real number p \in [0, 1] and choice of subsets S_n \subseteq \Gamma_n with | S_n | = (p + o(1)) | \Gamma_n | , the sequence of graphs \operatorname{BiCay}(\Gamma_n, S_n) is quasirandom.

Though quasirandomness can only be defined for sequences of groups, the concept of c -quasirandomness for specific groups can be extended to groups using the definition of c -quasirandomness for specific graphs. In fact, it can be shown that for any c -quasirandom group \Gamma , the number of solutions to xy=z with x \in X , y \in Y , and z \in Z is approximately equal to what one might expect if S was chosen randomly; that is, approximately equal to \tfrac .

This result follows from a direct application of the expander mixing lemma.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377484544 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.