All Articles

Arithmetic regularity with forbidden bipartite configurations

Szemeredi’s regularity lemma is a fundamental result in graph theory, which says that
sufficiently large finite graphs can be partitioned into a small number of pieces so that the edges
between most pairs of pieces are randomly distributed. In other words, the regularity lemma
processes finite graphs into ingredients that are either highly structured (namely, the partition of
the graph) or highly random (namely, the edges between regular pairs). In 2005, Green
introduced arithmetic regularity, which is a group-theoretic analogue of Szemeredi’s result.
Green’s work involves decompositions of finite abelian groups into algebraically structured
pieces, which behave randomly with respect to some chosen subset of the group. In this talk, I
will consider a set $A$ in an arbitrary finite group $G$, such that the bipartite graph on $G
\times G$ induced by $x\cdot y\in A$ omits some induced bipartite subgraph of size bounded
by a fixed integer $k$. I will present strengthened versions arithmetic regularity in this setting,
which yield algebraic structure theorems for sets $A$ as above. This work combines tools from
model theory, additive combinatorics, and the structure of compact topological groups. Joint
with A. Pillay and C. Terry.