The minimum of the graph likelihood
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.19467
curl -X POST /api/v1/records/arxiv/2608.19467/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.19467/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'