Departmental Colloquium
Lior Gishboliner
ETH Zurich
Global-to-local problems in discrete structures
Abstract: The key question of study in extremal graph theory can be stated as follows: How dense should a graph (or hypergraph) be globally in order to guarantee that it contains a given local structure? This global-to-local theme is also a key feature of the field of property testing, which deals with the design of randomized "election-polling"-type algorithms which infer global information about a graph from local samples. I will survey several interconnected topics in extremal graph theory and property testing, focusing on the influential Brown-Erdos-Sos conjecture and the removal lemma. I will also present new results on these topics.
Tuesday December 5, 2023 at 3:00 PM in 636 SEO