The Container Method
And its applications
J.N. Anemaet (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A. Bishnoi – Mentor (TU Delft - Discrete Mathematics and Optimization)
Ananthakrishnan Ravi – Mentor (TU Delft - Discrete Mathematics and Optimization)
JAM de Groot – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
In this thesis, we explore the method of hypergraph containers and its applications to problems in extremal combinatorics and discrete geometry. We start by introducing containers on triangle-free graphs and use it to give a lower bound on the number of triangle-free graphs on n vertices. We then generalise to the container algorithm for independent sets in graphs, which is a version of regular graphs. The proof of this theorem is an algorithm. We study this algorithm and apply it to the Erdős-Rényi random graph G(n,p). After this we expand to hypergraphs, specifically 3-uniform hypergraphs. Finally we look at the application to a problem in discrete geometry: Given n points in the Euclidean plane ℝ², with at most three on any line, how large a subset are we guaranteed to find in general position (i.e., with at most two on any line)? A strong upper bound is obtained by using the hypergraph container method.