On the query complexity of estimating the distance to hereditary graph properties

December 02, 2019 ยท The Ethereal ยท ๐Ÿ› SIAM Journal on Discrete Mathematics

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, Henrique Stagni arXiv ID 1912.01081 Category math.CO: Combinatorics Cross-listed cs.DS Citations 5 Venue SIAM Journal on Discrete Mathematics Last Checked 6 months ago
Abstract
Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $ฮ“$ to being induced $\mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan Regularity Lemma and on a Removal Lemma for $\mathcal{F}$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago