Polynomial Removal Lemma for Ordered Matchings
We prove that for every ordered matching $H$ on $t$ vertices, if an ordered $n$-vertex graph $G$ is $\varepsilon$-far from being $H$-free, then $G$ contains $\text{poly}(\varepsilon) 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.
Authors
- Lior Gishboliner (ORCID: https://orcid.org/0000-0003-0688-8111)
- Borna Šimić
Institutions
- ETH Zurich (CH)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-10-31
- DOI
- https://doi.org/10.37236/12629
- Citations
- 1
- Primary Topic
- Machine Learning and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.35
Funders
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung