Regularity inheritance in pseudorandom graphs

DOI10.1002/RSA.20851zbMATH Open1436.05093arXiv1606.01168OpenAlexW2963396951MaRDI QIDQ5113941FDOQ5113941

Authors:

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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$.

Full work available at URL: https://arxiv.org/abs/1606.01168

Recommendations

• Small subsets inherit sparse \(\varepsilon\)-regularity
• Counting in hypergraphs via regularity inheritance
• $L_p$ regular sparse hypergraphs
• Extremal results in sparse pseudorandom graphs
• Regular pairs in sparse random graphs I

zbMATH Keywords

counting lemmaregularity inheritancepseudorandom graphssparse regularity lemmaSzemerédi's regularity lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cited In (2)

• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs

This page was built for publication: Regularity inheritance in pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113941)