The Sparse Regularity Method with Schatten Norms and Entropy

Abstract

We introduce a regularity method for sparse graphs, with new regularity and counting lemmas which use the Schatten–von-Neumann norms to measure uniformity. This leads to $k$-cycle removal lemmas in subgraphs of mildly-pseudorandom graphs, and also in graphs lacking a quasi-smooth family of bipartite subgraphs, extending results of Conlon, Fox, Sudakov and Zhao. We give some additive-combinatorial applications: one about translation-invariant linear equations in subsets of mildly-pseudorandom sets, one about such equations in generalized Sidon sets, and one about polygonal patterns in subsets of $\mathbb{Z}^2$ with few parallelograms (giving a two-dimensional analogue for a result of Prendiville). Separately, our regularity lemma implies a dense graph removal lemma with mild constant dependencies, in graphs whose spectral $L^{2-\varepsilon}$ norms are small.