Graphs and Matroids Seminar - Amitha Vallapuram

Title: The Container method for Enumerating Triangle-free graphs

Abstract: The container method is a tool for bounding the number of independent sets in graphs and can be generalized to hypergraphs. It utilizes the observation that independent sets are found in clusters or “containers” within the graph. One application of this method is to bound the number of finite objects with some forbidden substructure. For example, we can bound the number of graphs on N vertices that do not contain K₃ as a subgraph, that is, the number of Triangle-free graphs on N vertices. We will take a look at finding this bound using the container method.