Polynomial removal lemma for ordered matchings

2023/07/04 by Lior Gishboliner, Gishboliner, Lior, Borna Šimić +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2307.01652

openalex publication_date 2023/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We prove that for every ordered matching H on t vertices, if an ordered n-vertex graph G is ε-far from being H-free, then G contains poly(ε) n^t copies of H. This proves a special case of a conjecture of Tomon and the first author. We also generalize this statement to uniform hypergraphs.

Cited by

• Polynomial Property Testing

Related

• Polynomial removal lemmas for ordered graphs
• Matchings avoiding ordered patterns
• Ordered Ramsey numbers of loose paths and matchings
• Extremal problems in ordered graphs
• Infinitely many counterexamples to a conjecture of Lovász