The 4-Sample Theorem on planar graphs

Abstract

The famous 4-Color Theorem from graph theory states that the vertices of any planar graph can be colored with four colors, so that no neighboring vertices have the same color. The 4-Sample Theorem from algebraic statistics says that the maximum likelihood estimator for a Gaussian graphical model of a planar graph exists with probability 1 if one has at least four samples. This number of necessary samples, the maximum likelihood threshold, is a new graph invariant from algebraic statistics and connected not only to parameter estimation, but also to matrix completion, the theory of filling partial matrices, and rigidity theory, which deals with stability of objects.