Szemeredi regularity lemma says something interesting about ALL finite graphs (specifically there is a decomposition of the graph into a "small" number of subgraphs, each of which is "quasirandom"). An "arithmetic" analogue, initiated by Ben Green tries to say something interesting about ALL pairs $(G,A)$ where $G$ is a finite group and $A$ a subset of $G$, noting that from this data one also obtains a bipartite graph $(G,G, E)$ where $(x,y)\in E$ iff $xy^{-1}\in A$.

In both the graph and arithmetic cases, better conclusions can be obtained by imposing more conditions on the graph relation or subset $A$ of $G$. For example one could restrict attention to all finite graphs which omit a given finite graph. I will focus on the case where the graph to be omitted is the "k-half graph". Likewise in the arithmetic case where the conclusion is that $A$ is close to being a union of cosets of a small index subgroup. I will also consider the more general framework where $G$ is an arbitrary amenable group and in place of a subset $A$ of $G$ we have a bounded function $f$ from $G$ to the reals.

(Joint work with Conant and Terry, and very recently with Conant.)