The minimum of the graph likelihood
Abstract
The likelihood of a finite simple undirected graph G on n vertices is the probability that the uniform sequential attachment process, which at each step joins a new vertex to a uniformly random subset of uniformly random size of the vertices already present, outputs a graph isomorphic to G. Dervovic, Mocherla and Severini conjectured that the likelihood is minimised by the balanced complete bipartite graph. We prove that, among complete bipartite graphs of a given order, the balanced one uniquely minimises the likelihood. Exact computation shows that it also minimises over all graphs for every order from $6$ through $14$. At n=15, the exact global minimisers are C5[K̅3] and its complement, giving the first counterexample. Completed exact searches show that the global minimisers at order $16$ are K8,8 and its complement. At order $17$, the unique minimiser is a self-complementary mixed blow-up of C5. At order $18$, the minimisers are K9,9 and its complement. We show that the failure is not sporadic by proving that the likelihood of the balanced complete bipartite graph is 2−(1/2−1/(8ln 2)+o(1))n2, whereas the minimum over all graphs of order n is 2−(1/2+o(1))n2, so the conjectured minimiser exceeds the minimum by a factor exponential in n2. We also determine the Shannon entropy of the process to leading order, namely n2/(4ln 2) bits, which shows that the conjectured minimiser is in fact more likely than a typical output of the process. The proofs rest on a vertex deletion recurrence which evaluates the likelihood in time O(2n n) and which closes on the blow-ups of any fixed base graph.
Related
- CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph
- Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area
- A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
- A Non-Asymptotic Gaussian Likelihood Theory for Long-Memory Toeplitz Models
- Restricted Maximum Likelihood Estimation in Generalized Linear Mixed Models
BibTeX
@misc{severini2026minimum,
title = {{The minimum of the graph likelihood}},
author = {Simone Severini and Eric W. Weisstein},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.19467},
eprint = {2608.19467},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19467},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The minimum of the graph likelihood
AU - Simone Severini
AU - Eric W. Weisstein
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2608.19467
UR - https://arxiv.org/abs/2608.19467
AB - The likelihood of a finite simple undirected graph G on n vertices is the probability that the uniform sequential attachment process, which at each step joins a new vertex to a uniformly random subset of uniformly random size of the vertices already present, outputs a graph isomorphic to G. Dervovic, Mocherla and Severini conjectured that the likelihood is minimised by the balanced complete bipartite graph. We prove that, among complete bipartite graphs of a given order, the balanced one uniquely minimises the likelihood. Exact computation shows that it also minimises over all graphs for every order from $6$ through $14$. At n=15, the exact global minimisers are C_5[K̅_3] and its complement, giving the first counterexample. Completed exact searches show that the global minimisers at order $16$ are K_8,8 and its complement. At order $17$, the unique minimiser is a self-complementary mixed blow-up of C_5. At order $18$, the minimisers are K_9,9 and its complement. We show that the failure is not sporadic by proving that the likelihood of the balanced complete bipartite graph is 2^−(1/2−1/(8ln 2)+o(1))n^2, whereas the minimum over all graphs of order n is 2^−(1/2+o(1))n^2, so the conjectured minimiser exceeds the minimum by a factor exponential in n^2. We also determine the Shannon entropy of the process to leading order, namely n^2/(4ln 2) bits, which shows that the conjectured minimiser is in fact more likely than a typical output of the process. The proofs rest on a vertex deletion recurrence which evaluates the likelihood in time O(2^n n) and which closes on the blow-ups of any fixed base graph.
ER -