北京雁栖湖应用数学研究院

本杰明·苏达科夫

Rajko Nenadov

2024年03月19日 17:05 至 18:15

Online

Zoom 787 662 9899 (BIMSA)

Hypergraph Containers theorem, obtained independently by Balogh, Morris, and Samotij and Saxton and Thomason, is one of the most influential discoveries in combinatorics in the last two decades. Briefly, given a hypergraph H with sufficiently uniformly distributed hyperedges, it states that every large independent set in H can be approximated from a small subset of its vertices. Made precise, this statement has far reaching consequences in random and extremal graph theory, and additive combinatorics. In the first part of the talk, I will motivate the statement of (a variant of) Hypergraph Containers through the lens of Janson's inequality. In the second part, I will discuss a new proof based on the second moment method. The main value of the proof lies in the simplicity and transparency of the ideas which, I believe, exploit the very essence of why the existence of hypergraph containers is not surprising. No previous knowledge about the topic is required.

Rajko Nenadov is a lecturer at the School of Computer Science of University of Auckland, New Zealand. Rajko obtained his PhD at 2016 from ETH Zurich under the supervision of Angelika Steger. Prior to joining the University of Auckland in July 2023, he spent two years as a postdoc of Nick Wormald at Monash University (Melbourne), another year as a postdoc of Benny Sudakov at ETH Zurich, and a few years working on search ranking at Google Zurich. His primary research interests are extremal and probabilistic combinatorics, and their applications in computer science. Rajko is currently supported by the Marsden Fund of the Royal Society of New Zealand.