pith. sign in

arxiv: 2504.19582 · v4 · submitted 2025-04-28 · 🧮 math.CO · cs.DS

Faithful universal graphs for minor-closed classes

Paul Bastide , Louis Esperet , Carla Groenland , Claire Hilaire , Cl\'ement Rambaud , Alexandra Wesolek This is my paper

Pith reviewed 2026-05-22 19:15 UTC · model grok-4.3

classification 🧮 math.CO cs.DS
keywords universal graphsminor-closed classesplanar graphsclique minorsexponential lower boundsinduced subgraphstreewidthpathwidth
0
0 comments X

The pith

A K_t-minor-free graph that contains every n-vertex planar graph as a subgraph must have 2^Ω(n) vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a finite quantitative version of an earlier infinite result: for any fixed t, any graph that avoids a K_t minor yet includes all planar graphs on n vertices as subgraphs must itself have exponentially many vertices in n. This shows that minor-closed structure imposes a size barrier when the host graph must serve as a universal container for a denser class like the planar graphs. The authors complement the lower bound with explicit constructions of polynomial-size hosts that work when the contained graphs are restricted to trees or to K_4-minor-free graphs and when induced subgraphs are allowed instead of arbitrary subgraphs. A reader cares because the result clarifies the tension between forbidding certain minors and still being able to embed all members of a richer minor-closed family.

Core claim

For any fixed t, if G is K_t-minor-free and contains every n-vertex planar graph as a subgraph, then the number of vertices in G is 2^Ω(n). The paper also constructs polynomial-size K_4-minor-free graphs that contain every n-vertex tree as an induced subgraph and polynomial-size K_7-minor-free graphs that contain every n-vertex K_4-minor-free graph as an induced subgraph, and it examines the orders of universal graphs that preserve bounded degree, treedepth, pathwidth or treewidth.

What carries the argument

The quantitative finite version of the Huynh-Mohar-Šámal-Thomassen-Wood result that links K_t-minor-freeness in the host with subgraph-universality for planar graphs to force exponential order.

If this is right

  • Universal graphs for the class of all planar graphs inside any fixed-minor-free host must grow exponentially with n.
  • When the contained class is restricted to trees and induced subgraphs are required, polynomial-size K_4-minor-free hosts exist.
  • When the contained class is restricted to K_4-minor-free graphs and induced subgraphs are required, polynomial-size K_7-minor-free hosts exist.
  • The order of structure-preserving universal graphs can be studied separately for bounded-degree, bounded-treedepth, bounded-pathwidth and bounded-treewidth classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same exponential barrier may appear for other pairs of minor-closed classes where one is strictly denser than the other.
  • It would be natural to ask whether the polynomial-size constructions extend to induced universality for additional minor-closed families beyond trees and K_4-minor-free graphs.
  • The result suggests that any attempt to build compact universal graphs for planar graphs must either allow larger minors or drop the minor-closed restriction on the host.

Load-bearing premise

That the minor-closed property of the host together with the requirement to contain all planar n-vertex graphs can be combined directly in the finite case to produce the exponential lower bound without further hidden restrictions.

What would settle it

An explicit K_t-minor-free graph on o(2^n) vertices that still contains every n-vertex planar graph as a subgraph would disprove the claimed lower bound.

Figures

Figures reproduced from arXiv: 2504.19582 by Alexandra Wesolek, Carla Groenland, Claire Hilaire, Cl\'ement Rambaud, Louis Esperet, Paul Bastide.

Figure 1
Figure 1. Figure 1: The construction of the subgraph-universal graph [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Examples of two simple 2-paths G(x) for x = (1, 1) and x = (1, 2). We count the number of isomorphism types we created. It is immediate that different x create different labelled graphs. Suppose that x and x ′ create isomorphic graphs G(x) and G(x ′ ) and let f : V (G(x)) → V (G(x ′ )) be a graph isomorphism. We have the following two properties: • f(1) ∈ {1, n}. Indeed, a graph isomorphism must preserve t… view at source ↗
Figure 3
Figure 3. Figure 3: Dividing a grid into four corners, four sides, and internal vertices. [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A triangulated 3 × 3 double grid (right) obtained from two disjoint triangulated 3×3 grids (left) by first adding a perfect matching between their boundaries (center) and then triangulating the 8 quadrangular faces created in the process. We view the resulting planar triangulation as being embedded on the sphere (or rather a cube). We now use Lemma 5.1 to prove the following variant for triangulated double… view at source ↗
Figure 5
Figure 5. Figure 5: The support of the four graph H1, . . . , H4. Every vertex which is not in a corner is far from the boundary in at least one of these four graphs. Note that each Hi is a triangulated ℓ × 2ℓ grid. Moreover, each vertex v of H is either in a τ -corner of G1 or G2, or v is τ -internal in some Hi for 1 ⩽ i ⩽ 4. Observe that each τ -corner of G1 or G2 contains at most τ 2 vertices, and since all jumps from M ar… view at source ↗
Figure 6
Figure 6. Figure 6: Illustration for the proof of Theorem 5.6. For the sake of clarity we only depict one of the two triangulated grids forming G1 and part of the boundary of the second grid. The red and blue vertices represent the shattered set A, and the blue vertices are the members of the subset B. Along a path P in the grid (in bold green and violet) we build disjoint subpaths of P between vertices in B via a vertex in A… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration for the proof of Lemma A.2. In red are depicted the local pairs in M2. In respectively green and blue are the set Dj and Uj for j ∈ [ℓ]. Informally, contracting these sets moves the crossings to the middle row. Lemma A.2. There is a polynomial function fA.2 : N>0 → N>0 such that the following holds. Let t, ℓ, ℓ′ be positive integers with ℓ, ℓ′ ⩾ 2fA.2(t). Let G be a triangulated ℓ × ℓ ′ grid. … view at source ↗
Figure 8
Figure 8. Figure 8: The rows of R and columns of C are in bold. Branch vertices are in red, and bags are depicted in light green. Jumps are depicted with dashed blue lines. a jump uv ∈ M. As dG(u, v) ⩽ 20t 2 , the probability that u and v are separated by a row of R or a column of C is at most 2 · 1 100t 2 · 20t 2 ⩽ 2 5 . It follows that in expectation, 3 5 |M| jumps of M are contained within two consecutive rows and columns … view at source ↗
read the original abstract

It was proved by Huynh, Mohar, \v{S}\'amal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed $t$, if a graph $G$ is $K_t$-minor-free and contains every $n$-vertex planar graph as a subgraph, then $G$ has $2^{\Omega(n)}$ vertices. On the other hand, we construct a polynomial size $K_4$-minor-free graph containing every $n$-vertex tree as an induced subgraph, and a polynomial size $K_7$-minor-free graph containing every $n$-vertex $K_4$-minor-free graph as induced subgraph. This answers several problems raised recently by Bergold, Ir\v{s}i\v{c}, Lauff, Orthaber, Scheucher and Wesolek. We study more generally the order of universal graphs for various classes (of graphs of bounded degree, treedepth, pathwidth, or treewidth), if the universal graphs retain some of the structure of the original class.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves a finite quantitative version of the 2021 result by Huynh, Mohar, Šámal, Thomassen and Wood: for any fixed t, every K_t-minor-free graph that contains every n-vertex planar graph as a subgraph has 2^Ω(n) vertices. It also gives explicit polynomial-size constructions of a K_4-minor-free graph containing every n-vertex tree as an induced subgraph and a K_7-minor-free graph containing every n-vertex K_4-minor-free graph as an induced subgraph. The authors further study the size of universal graphs that preserve bounded degree, treedepth, pathwidth or treewidth while remaining in the corresponding minor-closed class, answering several questions of Bergold et al.

Significance. The finite lower bound supplies a concrete size threshold that was only known in the infinite setting, while the matching-style polynomial constructions for the strictly smaller classes of trees and K_4-minor-free graphs demonstrate that the exponential blow-up is forced precisely by the full planar class. The additional results on structure-preserving universal graphs for bounded-width classes are technically independent and enlarge the scope of the work. If the proofs are correct, the manuscript resolves the finite analogues of the cited open problems and provides a template for quantitative universality statements in minor-closed families.

major comments (2)
  1. [Introduction / main theorem] §1 (Introduction) and the statement of the main lower bound: the argument proceeds by contradiction from |V(G)| = 2^{o(n)} and invokes the structural consequences of K_t-minor-freeness to bound the number of distinct n-vertex planar subgraphs; the manuscript should make explicit which excluded-minor theorem or treewidth bound is applied to obtain the exponential gap, because this step carries the entire quantitative claim.
  2. [Construction for trees] Construction section for the K_4-minor-free universal graph on trees: the polynomial degree is not stated in the abstract or introduction; if the construction uses a product or blow-up whose size is O(n^c), the value of c should be recorded so that the result can be compared directly with the exponential lower bound for the planar case.
minor comments (2)
  1. [Abstract] The abstract alternates between 'subgraph' and 'induced subgraph' when describing the universal graphs; the precise relation (subgraph versus induced) should be uniform in all theorem statements.
  2. [References / Introduction] The citation to the 2021 Huynh et al. paper appears only in the abstract; a full bibliographic entry and a brief comparison paragraph in the introduction would clarify how the finite proofs differ from the infinite argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment, and the recommendation of minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [Introduction / main theorem] §1 (Introduction) and the statement of the main lower bound: the argument proceeds by contradiction from |V(G)| = 2^{o(n)} and invokes the structural consequences of K_t-minor-freeness to bound the number of distinct n-vertex planar subgraphs; the manuscript should make explicit which excluded-minor theorem or treewidth bound is applied to obtain the exponential gap, because this step carries the entire quantitative claim.

    Authors: We agree that the quantitative lower bound rests on a specific structural fact about K_t-minor-free graphs. The proof applies the grid-minor theorem (in the form that every K_t-minor-free graph has treewidth bounded by a function of t and the size of the largest grid minor it can contain) together with the observation that planar graphs of treewidth w require at least 2^Ω(w) vertices to embed all of them. In the revised manuscript we will insert an explicit sentence in §1 and in the proof of the main theorem citing the precise statement of the grid-minor theorem (Robertson–Seymour–Thomas) and the resulting treewidth bound that produces the exponential gap. revision: yes

  2. Referee: [Construction for trees] Construction section for the K_4-minor-free universal graph on trees: the polynomial degree is not stated in the abstract or introduction; if the construction uses a product or blow-up whose size is O(n^c), the value of c should be recorded so that the result can be compared directly with the exponential lower bound for the planar case.

    Authors: We agree that an explicit polynomial degree improves readability and facilitates comparison with the exponential lower bound. The construction in Section 3 produces a K_4-minor-free universal graph of size O(n^3) for n-vertex trees (via a suitable product of a bounded-treewidth host graph with a small number of copies). We will add the concrete bound O(n^3) to both the abstract and the first paragraph of the introduction in the revised version. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper cites the 2021 external result (Huynh et al.) solely for the infinite-case motivation and supplies an independent finite quantitative proof via contradiction using K_t-minor-freeness structural restrictions. The polynomial-size constructions for trees and K_4-minor-free graphs are explicit and do not reduce to fitted parameters or self-referential definitions. No load-bearing self-citation chain, ansatz smuggling, or renaming of known results occurs; the derivation remains self-contained against the stated assumptions and external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies entirely on standard definitions from graph theory; no new parameters, axioms beyond background mathematics, or invented entities are introduced.

axioms (1)
  • standard math The minor relation is defined via edge deletions, contractions, and vertex deletions as standard in graph theory.
    Invoked to define K_t-minor-free graphs throughout the statements.

pith-pipeline@v0.9.0 · 5747 in / 1311 out tokens · 48773 ms · 2026-05-22T19:15:44.162623+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [1]

    Adjacency labeling schemes and induced-universal graphs

    arXiv:1404.3391. [Alo17] Noga Alon. Asymptotically optimal induced universal graphs. Geometric and Functional Analysis, 27(1):1–32, February 2017. [AN19] Noga Alon and Rajko Nenadov. Optimal induced universal graphs for bounded-degree graphs. Math. Proc. Camb. Philos. Soc. , 166(1):61–74, 2019. arXiv:1607.03234. [BCE+82] Laszlo Babai, Fan R. K. Chung, Pau...

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  2. [2]

    for every uv ∈ M , uv is local and u, v ∈ Ri ∪ Ri+1; and

    work page

  3. [3]

    We obtain the following as a simple consequence, where the local jumps are allowed to be scattered in the grid, instead of all concentrated on a central row

    |M | ⩾ fA.1(t); then Kt is a minor of G ∪ M . We obtain the following as a simple consequence, where the local jumps are allowed to be scattered in the grid, instead of all concentrated on a central row. 31 Figure 7: Illustration for the proof of Lemma A.2. In red are depicted the local pairs in M2. In respectively green and blue are the setDj and Uj for ...

    work page

  4. [4]

    for every uv ∈ M , uv is local and u, v are fA.2(t)-internal; and

    work page

  5. [5]

    down”-part of columnj and Uj the “upper

    |M | ⩾ fA.2(t); then Kt is a minor of G ∪ M . Proof. Let fA.2(t) = 1 + 2(fA.1(t) − 1)fA.1(t). Let j1 = i1 = fA.2(t), i2 = ℓ′ − fA.2(t) and j2 = ℓ − fA.2, which are the indices of the first and last internal rows and columns. First suppose that there exists j ∈ {j1, . . . , j2 − 1} such that the family M contains at least fA.1(t) pairs of vertices in Cj ∪ ...

    work page

  6. [6]

    for every uv ∈ M , dG(u, v) ⩽ 20t2 and u, v are fA.3(t)-internal; and

    work page

  7. [7]

    |M | ⩾ fA.3(t); then G ∪ M contains Kt as a minor. Proof. Consider a subset of columns C = Ci1, . . . , Cia with 1 = i1 < · · · < ia = ℓ and a subset of rows R = Rj1, . . . , Rjb with 1 = j1 < · · · < jb = ℓ′. Note that the corresponding vertices in G induce a subdivision H of the a × b grid. Call the vertices of G in the intersection of one of these rows...

    work page

  8. [8]

    It follows that in expectation, 3 5 |M | jumps of M are contained within two consecutive rows and columns ofR and C. Each region bounded by two consecutive rows and columns contains at most(100t2)2 vertices by definition, and since the jumps of M are pairwise disjoint, such a region contains at most (100t2)2 jumps of M. It follows that there is a choice o...

    work page

  9. [9]

    for every uv ∈ M , at least one of u, v is 20t2-internal

    work page

  10. [10]

    all the vertices that are an endpoint of a jump from M lie pairwise at distance more than 20t2 in G

    work page

  11. [11]

    We are now ready to prove the main result of this section, Lemma 5.1, which we restate below for convenience

    |M | ⩾ fA.4(t); then Kt is a minor of G ∪ M . We are now ready to prove the main result of this section, Lemma 5.1, which we restate below for convenience. Lemma 5.1. There is a polynomial function f5.1 : N>0 → N>0 such that the following holds. Let t be a positive integer, let ℓ, ℓ′ be integers with ℓ, ℓ′ ⩾ 2f5.1(t). Let G be a triangulated ℓ × ℓ′ grid. ...

    work page

  12. [12]

    for every uv ∈ M , u or v is f5.1(t)-internal; and

    work page

  13. [13]

    |M | ⩾ f5.1(t); then Kt is a minor of G ∪ M . Proof. Let f5.1(t) = fA.3(t) + (2(40t2 + 1)2 + 1)fA.4(t) + 20t2. Assume first thatM contains at least fA.3(t) jumps uv such that dG(u, v) ⩽ 20t2. Note that for such a pairuv, if at least one ofu, v is s-internal (for some constants) then both u and v are (s − 20t2)-internal. It follows that all jumps uv ∈ M wi...

    work page