Bounded Expansion via Hall Ratio in Shallow Minors

Problem 8 · arXiv:1812.07327

arXiv Problem high confidence— first stated 2020-01-30

Authors: Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu

Status open medium confidence

Problem 8 asks whether a graph class has bounded expansion if and only if the Hall ratio is uniformly bounded in all shallow minors. The forward direction is established in the source paper (Corollary 7 analogue). The converse remains open: no paper has been found that either proves or disproves it. The paper arXiv:2411.16465 (Steiner, 2024) was flagged as a candidate resolution but in fact addresses a distinct problem — whether χ_f is bounded by a function of ρ for individual graphs — and does not resolve the shallow-minor characterization of bounded expansion.

Reviewer notes. Neither verified internal reference resolves Problem 8. arXiv:2411.16465 was likely matched at fuzz=97 because it shares key terms (Hall ratio, fractional chromatic number) with the source paper and addresses a closely related but distinct problem. The conjecture dates to 2020; as of May 2026 no follow-up resolving the equivalence between bounded expansion and bounded Hall ratio in all shallow minors has been located. Confidence is medium rather than high because the paper is six years old and the absence of a follow-up in a relatively active area warrants caution.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Is it true that a class $\mathcal{C}$ has bounded expansion if and only if there exists a function $f_6 : \mathbb{N} \to \mathbb{N}$ such that for every $r \in \mathbb{N}$ and every $G \in \mathcal{C} \mathbin{\triangledown} r$, $\rho(G) \leq f_6(r)$?

Context

Corollary 7 gives an analogous characterisation of bounded expansion via $\chi_f$ in shallow minors. The forward direction (bounded expansion implies bounded Hall ratio in shallow minors) is clear; the converse argument fails by Theorem 2. Proposition 1 shows a nowhere-dense class with unbounded Hall ratio, but no class with unbounded expansion and bounded Hall ratio in all shallow minors is known.

Source paper

1-subdivisions, fractional chromatic number and Hall ratio
Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu · 2020-01-30
https://arxiv.org/abs/1812.07327 PDF source