Complete Graph Minors from Homological Graph Dimension

Definitions and mathematical statement

Let $G$ be a finite graph, and let $K_n$ denote the complete graph on $n$ vertices. A graph is a minor of $G$ if it can be obtained from $G$ by vertex deletions, edge deletions, and edge contractions. An induced subgraph on a vertex set contains every edge of $G$ whose endpoints lie in that set.

For a family $\mathcal H=(H_i)_{i\in I}$ of induced subgraphs of $G$, define its nerve by \[ N(\mathcal H)=\{\varnothing\}\cup\left\{J\subseteq I: J\text{ is finite and nonempty, and }\bigcap_{j\in J}V(H_j)\ne\varnothing\right\}. \] The supplied record describes $\gamma(G)$ as the largest homological degree $q$ for which some "connected family" of induced subgraphs has a nerve with nonzero $H_q$. It does not define "connected family" or specify homology coefficients.

To expose these unresolved choices, write $\mathcal C(G)$ for the intended class of such families and $A$ for a fixed nonzero coefficient group. With ordinary simplicial homology in nonnegative degrees, the proposed definition would be \[ \gamma_{\mathcal C,A}(G)=\max\left\{q\in{\mathbb{Z}}_{\ge0}:\exists\mathcal H\in\mathcal C(G),\ H_q\left(N(\mathcal H);A\right)\ne0\right\}, \] provided this maximum exists. These parameters display missing specifications; they do not assert that the source intended every possible choice.

The supplied question is whether, for the intended invariant $\gamma$, \[ \forall\,G\text{ finite}\quad\forall\,d\in{\mathbb{Z}}_{>0},\qquad \gamma(G)\ge d\quad\Longleftrightarrow\quad K_{d+2}\text{ is a minor of }G. \] A complete formulation requires the source's admissibility condition for families, its coefficient convention, and its convention when the defining set has no maximum, including the empty-graph case. No connectedness assumption on $G$ itself is supplied.

Short English statement

The question asks whether the homological dimension obtained from nerves of suitable families of induced subgraphs detects exactly the complete graph minors: dimension at least $d$ should correspond to a $K_{d+2}$ minor, for every finite graph and every positive integer $d$. The meaning of a suitable "connected family" and the homology conventions remain unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003463$, title "Complete Graph Minors from Homological Graph Dimension," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is identified; the supplied proposed year is 2017.
• Supplied report citation: Discrete Geometry (2018), Oberwolfach Reports, pp. 1135--1205, DOI 10.4171/owr/2017/19. https://doi.org/10.4171/owr/2017/19. The background describes these reports as documenting mathematical workshops and their open-problem discussions. The citation's 2018 designation and its relationship to the supplied 2017 year remain unverified.
• Supplied literature reference: On a minor-monotone graph invariant, DOI 10.1006/jctb.1995.1056. https://doi.org/10.1006/jctb.1995.1056. The record supplies no author list or precise location supporting the formulation.
• Literature checked at: 2026-08-21. This is supplied dated curation, not independently verified. Its assessment labels the problem open and reports that the equivalence detects $K_3$, $K_4$, and $K_5$ minors in the established low-dimensional cases, while the general equivalence remains open. The background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified, with the supplied explanation that mathematical content was preserved while notation, typography, and sentence structure were repaired for publication. This label is recorded as source metadata, not as independent mathematical verification of this draft.