When: Sunday, April 23, 10am
Where: Schreiber 309
Speaker: Nick Kushnir,
Tel Aviv University
Title:
Testing versus Estimation of Graph Properties, Revisited
A graph $G$'s distance to satisfying property ${\cal P}$ is the smallest $\alpha$ so that one can
turn
$G$ into a graph satisfying ${\cal P}$ using
$\alpha n^2$ edge modifications. Given a hereditary graph property ${\cal P}$, what is the smallest
$q=q_{\cal P}(\varepsilon)$ so that a random set of $q$ vertices of $G$ induces whp a subgraph
whose distance to ${\cal P}$ is within $\varepsilon$ of $G$'s distance to ${\cal P}$? A problem studied
in several
recent works asks if for every hereditary ${\cal P}$, the parameter $q$ is within a polynomial of the
parameters given by
the removal lemma associated
with ${\cal P}$. Our main result is an exponential bound for this problem, which improves upon a doubly
exponential bound of Hoppen, Kohayakawa, Lang, Lefmann and Stagni. We also obtain a doubly exponential
bound which applies to every graph property, improving over a tower-type bound of Fischer and Newman.
Our main conceptual contribution in this work is that we manage to turn a non-effective previous proof of
Fischer and Newman, into an efficient one by relying on the Frieze-Kannan weak regularity lemma. On the
technical
level, our main
contribution is in establishing certain properties of weak regular partitions that are of independent
interest.
Based on joint work with Lior Gishboliner and Asaf Shapira.