Removal lemmas with polynomial bounds

DOI10.1145/3055399.3055404zbMath1370.68323arXiv1611.10315OpenAlexW2558289754WikidataQ124956030 ScholiaQ124956030MaRDI QIDQ4977998

Lior Gishboliner, Asaf Shapira

Publication date: 17 August 2017

Published in: International Mathematics Research Notices, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

removal lemmagraph property testingpolynomially bounded removal lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (10)

A characterization of easily testable induced digraphs and \(k\)-colored graphs ⋮ Polynomial removal lemmas for ordered graphs ⋮ Efficient Removal Lemmas for Matrices ⋮ Efficient removal lemmas for matrices ⋮ On 3‐graphs with no four vertices spanning exactly two edges ⋮ Local-vs-global combinatorics ⋮ Unnamed Item ⋮ Efficient Testing without Efficient Regularity ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ Estimating parameters associated with monotone properties

This page was built for publication: Removal lemmas with polynomial bounds