Hosted Coloring Framework for Hypergraph Coloring Problems

Abstract

Hypergraph coloring and independent set problems are natural generalizations of their graph counterparts, which are canonical NP-hard problems central to combinatorial optimization. Compared to graphs, much less is known about hypergraph coloring and independent set problems. In particular, both problems are NP-hard and hard to approximate in the worst case, motivating the study of structured or average-case models where efficient algorithms may exist. In this thesis, we study coloring problems in r-uniform hypergraphs under planted and semi-random models. We first consider random hypergraphs with balanced planted k-colorings. We next study the hosted coloring framework for hypergraphs, extending ideas previously developed for graphs. The hosted coloring model helps one study different components of randomness separately and see which aspect of randomness makes the coloring problem easy. Our approach extends spectral and probabilistic techniques developed for graph coloring to the hypergraph setting, requiring new analyses to handle correlations in hypergraph adjacency matrices. These results provide algorithmic guarantees for hypergraph coloring in natural random and semi-random models, and contribute to understanding which structural properties enable efficient algorithms for otherwise intractable problems.