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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Polynomial Removal Lemma for Ordered Matchings

Lior Gishboliner, Borna Šimić
1 citations
The Electronic Journal of Combinatorics
Machine Learning and Algorithms
0.35
article

Polynomial Removal Lemma for Ordered Matchings

Lior Gishboliner, Borna Šimić
article en
1 citations

Abstract

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.

The Electronic Journal of CombinatoricsVol. 31(4)
ETH Zurich (CH)
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
Openalex Percentile: Top 32%
Machine Learning and Algorithms
0.35
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Polynomial Removal Lemma for Ordered Matchings — Lior Gishboliner, Borna Šimić · The Electronic Journal of Combinatorics (2024) | TGRS Research Map | TGRS