Computer Science/Discrete Mathematics Seminar II

The recently-discoverd Hypergraph Container Method (Saxton and Thomason, Balogh, Morris and Samotij), generalizing an earlier version for graphs (Kleitman and Winston), is used extensively in recent years in extremal and probabilistic combinatroics.  In essence, it shows that independent sets in regular-enough dense hypergraphs must be clustered in some fashion.

In this seminar we will give an overview of this method and then present its first algorithmic applications.  We use it algorithmically to convert algorithms into faster algorithms for regular or dense input instances.  An important component of our work is the generalization of graph containers to Partition Containers.  While standard containers apply to a single independent set, partition containers explore the structure of several independent sets at the same time. 

Our main application resolves a major open problem about Graph Coloring algorithms, for regular graphs.  The chromatic number of a graph can be computed in $2^n$ time (Husfeldt et al.).  For $k<=6$ it is known that $k$-coloring can be solved in $(2-eps)^n$ time for some $eps>0$.  For larger values of $k$ improvements are only known for sparse graphs.  We show that $k$-coloring of regular graphs can be solved in $(2-eps_k)^n$ time, where $eps_k>0$ for every $k$.  We stress that the degree of the regular graphs is unbounded. 

As another application, we give the first improved $k$-SAT algorithm for dense formulas.  We give additional applications including faster algorithms for unweighted and weighted Maximum Independent Set algorithms in regular graphs.