  The maximum likelihood threshold (MLT) of a graph $G$ is the minimum number
of samples to almost surely guarantee existence of the maximum likelihood
estimate in the corresponding Gaussian graphical model. We give a new
characterization of the MLT in terms of rigidity-theoretic properties of $G$
and use this characterization to give new combinatorial lower bounds on the MLT
of any graph.
  We use the new lower bounds to give high-probability guarantees on the
maximum likelihood thresholds of sparse Erd{\"o}s-R\'enyi random graphs in
terms of their average density. These examples show that the new lower bounds
are within a polylog factor of tight, where, on the same graph families, all
known lower bounds are trivial.
  Based on computational experiments made possible by our methods, we
conjecture that the MLT of an Erd{\"o}s-R\'enyi random graph is equal to its
generic completion rank with high probability. Using structural results on
rigid graphs in low dimension, we can prove the conjecture for graphs with MLT
at most $4$ and describe the threshold probability for the MLT to switch from
$3$ to $4$.
  We also give a geometric characterization of the MLT of a graph in terms of a
new "lifting" problem for frameworks that is interesting in its own right. The
lifting perspective yields a new connection between the weak MLT (where the
maximum likelihood estimate exists only with positive probability) and the
classical Hadwiger-Nelson problem.
