A probabilistic perspective on graph coloring

Abstract

Graph coloring is perhaps the most fundamental, deeply-studied, and well-known area in graph theory, with many of the most basic questions in the field still widely open. Graph coloring questions often have wide ranging applications across fields as diverse as statistical physics, theoretical computer science, route planning, disease spread, cybersecurity, circuit design, and network science more broadly. This thesis studies graph coloring from a probabilist’s perspective, focusing on graph coloring problems that share an underlying theme: given an exponentially large family of objects derived from a graph vertex-coloring, can we understand what a typical or random object in this large family looks like without manually searching through exponentially many alternatives? The majority of this thesis is centered around two basic graph coloring problems, each of which has been heavily studied and comes with a rich history and many applications. We begin this thesis by establishing a fourth moment phenomenon for the number of monochromatic copies of any fixed subgraph in a given graph sequence (when given at least eight colors). We also study, and in many special cases, characterize, failures of a fourth moment phenomenon to hold in the two-color regime. We then continue to our second major topic of study. We essentially resolve a folklore conjecture about the uniform distribution of proper colorings of a bounded-degree tree. As a consequence, we are able to make significant progress towards a longstanding conjecture in the statistical physics community and one of the oldest and most basic still-open questions in the field of approximate counting and sampling. We also disprove the efficacy of a particular, popular approach to tackling this pair of conjectures. Finally, we conclude the thesis by taking a different approach to studying typical samples from exponentially large families, applying the graph container method to study two coloring-adjacent questions: upper bounding the number of error correcting codes and understanding the structure of typical unit-distance avoiding sets in R².