14:00
15:00

A landmark result of Alon and Shapira characterises testable graph properties by showing that every such property can be described via the Szemerédi regularity lemma. Among the many results in graph property testing, the case of (induced) H-freeness has played a particularly central role, both because of its foundational importance and because of its deep connections with graph removal lemmas. In this talk, we present a finer-grained characterisation of the testability of hereditary properties, based on an appropriate clustering phenomenon. As applications, we obtain a characterisation of those hereditary properties that are easily testable by oblivious one-sided error testers, and we identify broad classes of instances for which the triangle removal lemma admits efficient bounds.

Joint work with Cameron Seth.

(Gaia Carenini) [University of Cambridge]

Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

English
LaBRI/178