Some Questions — Question 14

Definitions and mathematical statement

The source asks for a quantitative version of an asserted compactness consequence: for every $\varepsilon>0$, every finite graph can be approximated to error $\varepsilon$ by a graph of bounded size $K(\varepsilon)$, independently of the graph being approximated. The record does not define approximation error or graph size, and it does not specify a graph metric, normalization, or degree restrictions.

Conditionally, if $\mathcal G$ is the intended class of finite graphs, $d$ its intended approximation pseudometric, and size means vertex count, the bound sought would be an explicit finite function $K:(0,\infty)\to{\mathbb{N}}$ such that \[ \forall\varepsilon>0\ \forall G\in\mathcal G\ \exists H\in\mathcal G: \quad |V(H)|\le K(\varepsilon),\qquad d(G,H)<\varepsilon. \] One could ask to estimate the optimal envelope \[ K_{\mathcal G,d}(\varepsilon)= \sup_{G\in\mathcal G}\min\{|V(H)|:H\in\mathcal G,\ d(G,H)<\varepsilon\}, \] with an empty feasible set assigned value $\infty$. This is only a conditional formulation: neither $\mathcal G$, $d$, nor the interpretation of size is supplied. The literal phrase "of size $K$" also does not distinguish exact size from an upper bound. Different graph-limit topologies or error measures produce different quantitative questions, so none is silently selected.

The supplied research summary labels the question OPEN-TRIAGE, describes existence as essentially compactness, and says no explicit estimate is known to its author and an effective version appears unresolved. That wording is a limited supplied assessment, not a verified claim that no estimate exists.

Short English statement

Estimate how large a finite graph must be to approximate any finite graph to a prescribed error. The approximation notion, graph class, and meaning of size are missing, so a definite quantitative problem cannot yet be extracted.

Sources

• Local UnsolvedMath registry, permanent ID $1200014$, exact source code catalogue entry, "Some Questions --- Question 14."
• Abert, Some questions (2010), Question 14. Supplied author-hosted source: https://www.renyi.hu/~abert/questions.pdf; manual transcription; recorded access 2026-07-29.
• Supplied OPEN-TRIAGE research summary, without a separate authoritative citation for the compactness theorem, its metric setting, or current quantitative bounds.