The minimum of the graph likelihood
summary
The gist
The likelihood of a finite simple undirected graph G on n vertices is the probability that the uniform sequential attachment process outputs a graph isomorphic to G…
In short
This paper investigates a graph likelihood invariant, which measures how probable a specific graph is produced by a random sequential attachment process. Researchers conjectured this likelihood is minimized by balanced complete bipartite graphs. While verified for many orders, they found the conjecture fails at n=15 with counterexamples like C5[K3]. The analysis shows the conjectured minimizer is significantly more likely than typical outputs.
Key concepts
- Likelihood Invariant
- This invariant quantifies the probability that a specific graph G is generated by a random sequential attachment process. It acts as a graph-theoretic analogue to the infinite monkey theorem, measuring how easily a structure can be produced without prior knowledge of what has already been built.
- Uniform Sequential Attachment Process
- This is the mechanism used to generate graphs. At each step, a new vertex is added by joining it uniformly at random to a subset of existing vertices that is also chosen uniformly at random in size. This process generates graphs based on purely random choices.
- Balanced Complete Bipartite Graph
- This specific type of graph, denoted as K(p, p), is the graph conjectured to have the minimum likelihood among complete bipartite graphs of a given order. The paper explores how this structure performs compared to other possible graphs.
Terminology used across episodes
This episode discusses
- The minimum of the graph likelihood · Paper Radio
- A notion of graph likelihood and an infinite monkey theorem
- Constructing graphs with limited resources
The paper
The minimum of the graph likelihood · Read on arXiv
Simone Severini, Eric W. Weisstein
University College London · Wolfram Research
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/(8 2)+o(1))n squared, whereas the minimum over all graphs of order n is 2-(1/2+o(1))n squared, so the conjectured minimiser exceeds the minimum by a factor exponential in n squared. We also determine the Shannon entropy of the process to leading order, namely n 2/(4 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.
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "The minimum of the graph likelihood".
Emmy: Here's the gist of the paper. The likelihood of a finite simple undirected graph G on n vertices is the probability that the uniform sequential attachment process outputs a graph isomorphic to G, and this invariant shows that among complete bipartite graphs of a given order, the balanced one uniquely minimizes this likelihood The Likelihood Invariant The likelihood of a finite simple undirected graph G on n vertices is defined as the probability that the uniform sequential attachment process outputs a graph isomorphic to G This invariant was introduced by Banerji, Mansour and Severini as a graph-theoretic analogue of the infinite monkey theorem It quantifies how easily a graph is produced by a mechanism that uses no information about the graph built so far The invariant satisfies L(G) = 1, where the sum runs over one representative of each isomorphism class of graphs with n vertices Conjecture and Refutation Dervovic, Mocherla and Severini conjectured that the likelihood is minimised by the balanced complete bipartite graph The conjecture states that for n ≥ 6, if n = 2p the minimum of L over graphs of order n is attained by Kp,p, and if n = 2p − 1 it is attained by Kp−1,p The computations verify this conjecture through n = 14 However, the central result is that the conjecture is false with its first failure at n = 15 Counterexamples and Asymptotics Theorem 5 shows that Conjecture 1 is false for n = 15, as L(C5
K3: ) = 0.20128...
Ada: times L(K7,8) This counterexample, the blow-up of the five cycle by independent sets of size three, is a triangle-free vertex-transitive graph that contradicts the second half of the heuristic Theorem 6 proves that as n → ∞, log2 1/L(K⌊n/2⌋,⌈n/2⌉) = 1/2 − 1/(8 ln 2)n squared + O(n log n), while the minimum over all graphs of order n is log2 minG L(G) = n 4 / (4 ln 2) + O(n log n) Computational Verification and Bounds The proof relies on a vertex deletion recurrence which evaluates the likelihood in time O(n 2/n) This recurrence closes on the blow-ups of any fixed base graph Exact computation for n ≤ 12 verifies Theorem 3, showing the minimum is attained exactly by K⌊n/2⌋,⌈n/2⌉ and its complement The complexity of L remains open Entropy and Typical Output Theorem 7 computes the Shannon entropy of the distribution L on isomorphism classes to be n 2/4 ln 2 + O(n log n) bits This shows that the conjectured minimiser sits above it, as In/n squared p → 1/(4 ln 2) The process concentrates on a 2(1/2 - 1/(4 ln 2))n 2+o(n 2) fraction of all isomorphism classes while still spreading over 2Θ(n 2) of them Maximum Likelihood The maximum, and open problems, indicate that no analogue of Theorem 2 is available for the maximum The order of magnitude for maxG L(G) remains 2Θ(n)/n!
Paper summary: Ada: So, we're looking at this paper "The minimum of the graph likelihood," and it’s diving into how hard it is to produce a specific graph using that random sequential attachment process.
Emmy: Basically, the central idea here is that there’s a minimum value for this likelihood among all graphs on a given number of vertices, and the authors are looking at what those minimums are.
Kolya: The paper starts by setting up this likelihood as an invariant of the graph, which is important because it means we can measure how likely a graph is to appear from that process without having to track every single step.
Ada: Exactly, and they're building on some older ideas here about what the minimum should be. They mention Dervovic, Mocherla, and Severini conjectured that the balanced complete bipartite graph minimizes this likelihood.
Emmy: But their main claim is actually that among complete bipartite graphs of a certain order, only the balanced one truly minimizes it. They’re proving that this specific structure is unique for those cases.
Kolya: And they extend those computations, showing that this same balanced complete bipartite graph also minimizes the likelihood over *all* possible graphs for orders from six up to fourteen.
Ada: That’s a significant extension because it suggests the balanced complete bipartite graph isn't just special among a subset of graphs, but genuinely minimal across the board for those sizes.
Emmy: But then they hit a wall at order fifteen, which is where things get interesting because they find the first counterexample to that conjecture.
Kolya: That counterexample involves the blow-up of the five cycle by independent sets of size three, and it’s a triangle-free vertex-transitive graph.
Ada: The paper quantifies this difference, showing that for order fifteen, the likelihood of that specific structure is about point two hundred percent times lower than it is for the balanced complete bipartite graph.
Emmy: That means even though the conjecture holds up to fourteen, it fails at fifteen because there’s a different structure doing better than what we thought was the best.
Kolya: And they also look at what happens as you get larger, showing that this failure isn't just a fluke by comparing the likelihood of the balanced complete bipartite graph to the minimum over all graphs.
Ada: The paper gives us a big picture here by showing that while their conjectured minimiser is relatively likely, it still falls short of the absolute minimum for larger numbers.
Emmy: They quantify this gap, showing that as n gets bigger, the ratio between the likelihood of the balanced complete bipartite graph and the true minimum grows exponentially with n squared.
Kolya: And they also calculate what we call Shannon entropy for this likelihood distribution, and it shows that at leading order, the process is concentrating on a fraction of all possible graphs that is about two to the power of half minus one over eight ln two times n squared.
Ada: That means the conjectured minimiser is actually more likely than just a typical output from this attachment process when you look at those counts.
Emmy: And they show that their proof relies on a vertex deletion recurrence, which is efficient enough to handle these kinds of graph structures, closing on the blow-ups of any fixed base graph.
Kolya: The limitation they mention is that the computation for this likelihood runs in time proportional to two to the n times n, so while it's good for smaller graphs, it doesn't scale up easily without more work.
Ada: So what we have here is a very detailed look at where our current understanding of graph likelihood minimization breaks down.
Emmy: And they’re leaving us with this counterexample at fifteen, which forces us to rethink the basic structure that minimizes this probability.
Kolya: The main thing for someone listening is that it shows the naive expectation about complete bipartite graphs being the best isn't always true, even when you look at small numbers like fifteen.
Ada: And they show how big the gap between their predicted minimum and the actual minimum gets as n increases, which really highlights how sensitive this problem is to graph structure.
Emmy: Ultimately, the paper "The minimum of the graph likelihood" uses these exact computations to test a long-held conjecture and finds that the minimiser isn't as simple as we first thought.
Conclusion: Ada: So we've been diving into this paper about the likelihood of graphs, specifically trying to find where that likelihood hits its lowest point for a given number of vertices and what that tells us about how these random processes work.
Emmy: Exactly, so we've seen how they look at the balanced complete bipartite graph and how it performs in those calculations.
Kolya: And we've seen the big sticking point, which is this counterexample at fifteen where things don't line up with what they first guessed was true for all sizes.
Ada: So to wrap up this part, the paper is really focused on showing that this likelihood doesn't have one simple answer anymore; it depends heavily on the exact number of vertices you start with.
Emmy: It seems like the authors are proving that while we had a good idea about what should be minimal for complete bipartite graphs, there are other structures that beat them out at certain scales.
Kolya: The main thing is that as you get bigger, the gap between their predicted minimum and what's actually possible gets pretty massive, it grows exponentially with the size of the graph.
Ada: And they do give us some numbers on how fast this gap opens up, which shows that these structural differences become very pronounced very quickly.
Emmy: It really highlights that just because a structure is good for small numbers doesn't mean it's good for everything.
Kolya: This leads us to think about what happens when we try to find the absolute best way to generate any graph from this process, and that's where things get interesting next.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors