{"id":"arxiv/2608.19467","url":"https://arxiv.org/abs/2608.19467","tags":["math.CO"],"score":0,"title":"The minimum of the graph likelihood","domain":"math.CO","source":"arxiv","authors":["Simone Severini","Eric W. Weisstein"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}