Hypergraph Containers via the second momemt method | Research seminar in Discrete Mathematics

Abstract

Hypergraph Containers theorem, obtained independently by Balogh, Morris, and Samotij andSaxton and Thomason, is one of the most influential discoveries in combinatorics in the last twodecades. Briefly, given a hypergraph H with suficiently uniformly distributed hyperedges, it statesthat every large independent set in H can be approximated from a small subset of its verticesMade precise, this statement has far reaching conseguences in random and extremal graph theoryand additive combinatorics. In the first part of the talk, l will motivate the statement of (a variant ofHypergraph Containers through the lens of Janson's ineguality. in the second part, l will discuss anew proof based on the second moment method. The main value of the proof lies in the simplicitand transparency of the ideas which, l believe, exploit the very essence of why the existence ofhypergraph 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, NewZealand. Rajko obtained his PhD at 2016 from ETH Zurich under the supervision of AngelikaSteger. Prior to joining the University of Auckland in July 2023, he spent two years as a postdoc ofNick Wormald at Monash University (Melbourne). another year as a postdoc of Benny Sudakov atETH Zurich, and a few years working on search ranking at Google Zurich. His primary researchinterests are extremal and probabilistic combinatorics, and their applications in computer scienceRajko is currently supported by the Marsden Fund of the Royal Society of New Zealand.