Hypergraph Containers via the second momemt method
Organizer
Benjamin Sudakov
Speaker
Rajko Nenadov
Time
Tuesday, March 19, 2024 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
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.
Speaker Intro
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.