The sparse regularity method with Schatten norms and entropy

2023/05/15 by Alexandru Pascadi, Pascadi, Alexandru
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Spectral Theory in Mathematical Physics

paper · pdf · doi:10.48550/arxiv.2305.08567

openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 applications in additive combinatorics: 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 Z² 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-ε norms are small.

Related

• A Unified View of Graph Regularity via Matrix Decompositions
• The regularity method for graphs with few 4-cycles
• Szemerédi's Regularity Lemma for matrices and sparse graphs
• Regularity inheritance in pseudorandom graphs
• Blow-up lemma for cycles in sparse random graphs