Local Count Thresholds for Bounded-Degree Embeddings

Definitions and mathematical statement

The supplied question asks for the least local-count threshold $f_k(\Delta)$ that forces embeddings of every $n$-vertex graph of maximum degree at most $\Delta$. The record does not supply enough definitions or hypotheses to specify this function precisely.

For an ordinary finite graph $H$, write $V(H)$ for its vertex set and $\Delta(H)=\max_{v\in V(H)}\deg_H(v)$ for its maximum degree when $V(H)\ne\varnothing$. Under the ordinary, non-induced graph-embedding interpretation, $H\hookrightarrow G$ means that there exists an injective map $\phi:V(H)\to V(G)$ such that $\{u,v\}\in E(H)$ implies $\{\phi(u),\phi(v)\}\in E(G)$. These conventions describe one possible interpretation; the supplied record does not establish the intended graph class or embedding convention.

With $G$ denoting the unspecified host, the requested implication can only be displayed schematically as \[ \begin{gathered} \text{all required local $k$-uniform homomorphism counts match}\\ \text{for every test graph $F$ with $\lvert V(F)\rvert\le m$} \end{gathered} \quad\Longrightarrow\quad \forall H\;\left(\lvert V(H)\rvert=n\ \text{and}\ \Delta(H)\le\Delta \ \Longrightarrow\ H\hookrightarrow G\right). \] The intended target is the least admissible $m=f_k(\Delta)$ for which the fully specified implication holds. This display is not a complete quantified conjecture: the local counts, the objects or reference values being matched, the meaning of $k$-uniform, the admissible hosts and targets, and the quantification of $n$ are absent. The record also leaves exact versus approximate matching and any size, density, error, or asymptotic hypotheses unspecified. Consequently, neither the admissible thresholds nor their minimum are defined by the supplied evidence.

Short English statement

Determine how large the test graphs must be so that matching the intended local homomorphism counts guarantees every bounded-degree spanning-size target embedding described by the source. The count condition, host hypotheses, and quantifiers are missing, so this remains an incomplete statement requiring reconstruction from the cited report.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005348$, title: Local Count Thresholds for Bounded-Degree Embeddings; exact source problem code: catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year 2023; no individual proposer is supplied.
• Supplied report citation: Combinatorics (2023), Oberwolfach Reports, DOI 10.4171/owr/2023/1, pp. 5--89. https://doi.org/10.4171/owr/2023/1. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions. No precise page or theorem locator for this question is supplied.
• Supplied literature source: Allen--Bottcher--Davies--Hng--Skokan, Approximate Blow-up Lemma. https://doi.org/10.1016/j.procs.2021.11.048.
• Literature assessment dated 2026-08-22: the supplied curation labels the problem open, states that the exact dependence on $k$ and $\Delta$ is unknown, and reports that an embedding theorem records only an $\Omega(\Delta)$ lower bound with no matching characterization. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. Its time-sensitive status and cited claims require independent verification.
• The registry labels the statement corrected_verified and reports that it was checked against the official Oberwolfach report and preserves its hypotheses, notation, and target. This is supplied verification metadata, not verification performed for this draft. The full report passage needed to resolve the missing definitions is absent from the supplied record.