Regularity inheritance in pseudorandom graphs

2016/06/03 by Peter Allen, Allen, Peter, Julia Böttcher +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1606.01168

openalex publication_date 2016/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox and Zhao [Adv. Math. 256 (2014), 206--290]. These inheritance lemmas also imply improved H-counting lemmas for subgraphs of bijumbled graphs, for some H.

Citations

• Blow-up lemmas for sparse graphs

Cited by

• Combinatorial theorems relative to sparse sets

Related

• Regularity inheritance in hypergraphs
• Notes on the Linear Algebraic View of Regularity Lemmas
• The sparse regularity method with Schatten norms and entropy
• Regular partitions of gentle graphs
• Revealing Structure in Large Graphs: Szemer 'edi's Regularity Lemma and\n its Use in Pattern Recognition