Further applications of the Container Method

Abstract

Recently, Balogh--Morris--Samotij and Saxton--Thomason proved that hypergraphs satisfying some natural conditions have only few independent sets. Their main results already have several applications. However, the methods of proving these theorems are even more far reaching. The general idea is to describe some family of events, whose cardinality a priori could be large, only with a few certificates. Here, we show some applications of the methods, including counting $C_4$-free graphs, considering the size of a maximum $C_4$-free subgraph of a random graph and counting metric spaces with a given number of points. Additionally, we discuss some connections with the Szemerédi Regularity Lemma.

This is a survey style paper written for the IMA volume "Recent Trends in Combinatorics" for the 2014-2015 Annual Thematic Program Discrete Structures: Analysis and Applications at the Institute for Mathematics and its Applications during Fall 2014

References in corpus (2)

• Combinatorial theorems relative to a random set
• The number of the maximal triangle-free graphs

Cited by in corpus (18)

• Iterated Elliptic and Hypergeometric Integrals for Feynman Diagrams
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• The normalized Laplacian spectrum of subdivisions of a graph
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Induced and non-induced poset saturation problems
• The Higher-Dimensional Skeletonization Problem
• $Q$-Laguerre spectral density and quantum chaos in the Wishart-Sachdev-Ye-Kitaev model
• Ehrhart polynomials of rank two matroids
• Exact and asymptotic enumeration of cyclic permutations according to descent set
• Triangles in graphs without bipartite suspensions
• The CDE property for skew vexillary permutations
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• A weighted cellular matrix-tree theorem, with applications to complete colorful and cubical complexes
• Extremal Numbers of Hypergraph Suspensions of Even Cycles
• Obstructions for partitioning into forests and outerplanar graphs
• Some orientation theorems for restricted DP-colorings of graphs
• $P$-strict promotion and $Q$-partition rowmotion: the graded case
• Asymptotics of self-overlapping permutations