Lior Gishboliner : Global-to-local problems in discrete structures

Posted by Vishesh Jain , part of the Departmental Colloquium.

At

Dec. 5, 2023, 3 p.m.

In

636 SEO

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.