Regularity inheritance in pseudorandom graphs

DOI10.1002/RSA.20851MaRDI QIDQ5113941zbMATH OpenOpenAlexFDO

Authors

Publication date 19 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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

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

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)