Vertex-minor universality of a random graph
Pith reviewed 2026-05-15 11:08 UTC · model grok-4.3
The pith
A random graph G(n,p) contains every graph on Ω(p√n) vertices as a vertex-minor with probability 1−2^{−Ω(p²n)} for p at least Ω(log n/√n).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We confirm that with probability 1−2^{−Ω(p²n)}, the random graph G(n,p) is Ω(p√n)-vertex-minor universal (up to an extra logarithmic factor) whenever Ω(log n/√n)≤p≤1/2. Together with a complementary result for the smaller-p regime, the full conjecture is thereby established.
What carries the argument
The vertex-minor relation, formed by a sequence of vertex deletions and local complementations that flip all edges inside the neighborhood of the chosen vertex.
If this is right
- Every k-vertex graph appears as a vertex-minor inside G(n,p) with probability at least 1−2^{−Ω(p²n)} for k up to the stated threshold.
- The same universality holds symmetrically for G(n,1−p).
- Combining the present range with the complementary result for p between 1/√n and n^{−1/3} covers the entire conjectured interval down to ω(1/√n).
- The failure probability decays exponentially in p²n, which is strong enough to survive union bounds over polynomially many choices of target graphs.
Where Pith is reading between the lines
- The result suggests that the vertex-minor closure of a typical random graph is already dense at linear size in p√n, which may yield new bounds on the minimum number of local complementations needed to realize small graphs.
- Similar embedding arguments could be adapted to other minor-like relations that combine deletions with local rewiring operations.
- The exponential tail bound opens the possibility of proving that a single random graph simultaneously contains many different small vertex-minors without increasing the failure probability appreciably.
Load-bearing premise
The concentration bounds used to guarantee the existence of the required vertex-minor embeddings continue to hold across the stated range of p without stronger dependence introduced by the local complementation steps.
What would settle it
Explicitly constructing or sampling a G(n,p) instance in the given p-range together with one fixed k-vertex graph that cannot be recovered from it by any sequence of vertex deletions and local complementations would falsify the claim.
read the original abstract
Given a graph $G$ and a vertex $v\in V(G)$, a local complementation at $v$ on $G$ is an operation that replaces the induced graph on the neighborhood of $v$ by its complement. A graph $H$ is a vertex-minor if $H$ can be obtained from $G$ by a sequence of vertex deletions and local complementation. A graph is said to be $k$-vertex-minor universal if it contains every $k$-vertex graph on any $k$-subset of vertices as a vertex minor. Previously, Ascoli--Fredrickson--Fredrickson--McFarland--Post proved that with high probability $G(n,1/2)$ is $\Omega(\sqrt{n})$-vertex-minor universal. Furthermore, they conjectured that with high probability $G(n,p)$ and $G(n,1-p)$ are $\Omega(p\sqrt{n})$-vertex-minor universal for all $\omega(1/\sqrt{n})\le p\le 1/2$. In this short note, we confirm this conjecture up to an extra logarithm factor and show that this is true with probability $1-2^{-\Omega(p^2n)}$ if $\Omega(\log n/\sqrt{n})\le p\le 1/2$. Together with a complementary result which applies to the regime where $1/\sqrt{n}\le p\le n^{-1/3}$ produced by an internal model at OpenAI, the conjecture is fully confirmed.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the Erdős–Rényi graph G(n,p) is k-vertex-minor universal with probability 1−2^{−Ω(p²n)} whenever Ω(log n/√n)≤p≤1/2 and k=Ω(p√n/log n). This confirms the Ascoli–Fredrickson–Fredrickson–McFarland–Post conjecture up to a single logarithmic factor in the universality scale; the authors note that a complementary argument (produced externally) covers the remaining regime 1/√n≤p≤n^{−1/3}.
Significance. If the concentration arguments are valid, the result supplies a clean, high-probability statement that nearly matches the conjectured threshold Ω(p√n) and closes the gap between the dense regime already settled by Ascoli et al. and the sparser regime treated by the external model. The explicit failure probability 2^{−Ω(p²n)} is stronger than the usual “with high probability” statements and would be a useful quantitative strengthening.
major comments (1)
- [Main probabilistic argument (proof of the stated theorem)] The central probabilistic estimate (implicitly used to bound the number of vertex-minor embeddings after local complementations) applies Chernoff-type tail bounds directly to edge indicators in G(n,p). Because each local complementation at a vertex v flips the entire neighborhood N(v), the edge indicators for distinct candidate embeddings are dependent; the maximum degree of dependence is Θ(k) per complementation sequence. Without an explicit dependency-graph or bounded-differences argument that absorbs this degree into the exponent, the union bound over binom(n,k)·(number of complementation sequences) may exceed 2^{−Ω(p²n)} once p=Θ(log n/√n).
minor comments (2)
- The abstract refers to a “complementary result … produced by an internal model at OpenAI” without a citation or short description; adding a sentence or footnote would improve readability.
- Notation for the vertex-minor relation and the precise definition of k-vertex-minor universality could be restated once in the introduction for readers who encounter the paper independently of Ascoli et al.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying the need to make the dependence handling explicit in the probabilistic argument. We address the point below and will revise the manuscript to include the missing details.
read point-by-point responses
-
Referee: [Main probabilistic argument (proof of the stated theorem)] The central probabilistic estimate (implicitly used to bound the number of vertex-minor embeddings after local complementations) applies Chernoff-type tail bounds directly to edge indicators in G(n,p). Because each local complementation at a vertex v flips the entire neighborhood N(v), the edge indicators for distinct candidate embeddings are dependent; the maximum degree of dependence is Θ(k) per complementation sequence. Without an explicit dependency-graph or bounded-differences argument that absorbs this degree into the exponent, the union bound over binom(n,k)·(number of complementation sequences) may exceed 2^{−Ω(p²n)} once p=Θ(log n/√n).
Authors: We agree that an explicit treatment of dependence is required for rigor. In the proof, each bad event is defined for a fixed k-set and a fixed sequence of local complementations; the Chernoff bound is applied to the (deterministically transformed) edge indicators of the resulting graph on that set. The dependency graph among these events has maximum degree O(k^3 2^{O(k)}), arising from sequences that share at least one vertex. Because the per-event failure probability is at most 2^{-Ω(p^2 k^2)} and the total number of events is at most binom(n,k)·(number of sequences) ≤ 2^{O(k log n + k log k)}, the union bound remains 2^{-Ω(p^2 n)} once the constants hidden by Ω are chosen sufficiently large. At the threshold p = Θ(log n/√n) we have k = Θ(log n) and both the union-bound overhead and the exponent p^2 n are Θ(log^2 n), so the inequality holds. We will add a short paragraph containing this dependency-graph calculation and the constant verification in the revised version. revision: partial
Circularity Check
No circularity: direct probabilistic proof from concentration and union bounds
full rationale
The paper establishes the stated vertex-minor universality result for G(n,p) via a self-contained probabilistic argument: it bounds the probability that a random graph contains every k-vertex graph on k-subsets as a vertex-minor, using concentration inequalities and a union bound over candidate embeddings and local-complementation sequences. No parameter is fitted to data and then relabeled as a prediction; no load-bearing step reduces to a self-citation whose authors overlap with the present work; the cited prior result (Ascoli et al.) is external and supplies only the conjecture being proved, not the derivation itself. The claimed probability 1-2^{-Ω(p²n)} follows from the explicit union-bound calculation rather than from any definitional identity or ansatz smuggled via citation. The derivation is therefore independent of its own outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard properties of the Erdős–Rényi model G(n,p) and the definition of vertex-minors via deletions and local complementations
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.