Download this article
 Download this article For screen
For printing
Recent Issues
Volume 15, Issue 1
Volume 14, Issue 2
Volume 14, Issue 1
Volume 13, Issue 1
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 2
Volume 11, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN (electronic): 2693-3004
ISSN (print): 2693-2997
Author Index
To Appear
Other MSP Journals
Computing maximum likelihood thresholds using graph rigidity

Daniel Irving Bernstein, Sean Dewar, Steven J. Gortler, Anthony Nixon, Meera Sitharam and Louis Theran

Vol. 14 (2023), No. 2, 287–305

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 recently proved a new characterization of the MLT in terms of rigidity-theoretic properties of G. This characterization was then used to give new combinatorial lower bounds on the MLT of any graph. We continue this line of research by exploiting combinatorial rigidity results to compute the MLT precisely for several families of graphs. These include graphs with at most nine vertices, graphs with at most 24 edges, every graph sufficiently close to a complete graph and graphs with bounded degrees.

maximum likelihood threshold, Gaussian graphical model, combinatorial rigidity, generic completion rank, graph rigidity
Mathematical Subject Classification
Primary: 52C25, 62H12
Received: 20 October 2022
Revised: 21 June 2023
Accepted: 30 June 2023
Published: 16 May 2024
Daniel Irving Bernstein
Department of Mathematics
Tulane University
New Orleans, LA
United States
Sean Dewar
School of Mathematics
University of Bristol
United Kingdom
Steven J. Gortler
Department of Computer Science
Harvard University
Cambridge, MA
United States
Anthony Nixon
Department of Mathematics and Statistics
Lancaster University
United Kingdom
Meera Sitharam
Department of Computer and Information Science and Engineering
University of Florida
Gainesville, FL
United States
Louis Theran
School of Mathematics and Statistics
University of St Andrews
St Andrews
United Kingdom