Blow-Ups of Clique Subdivisions in Dense Graphs

Definitions and mathematical statement

For integers $m,r\geq 2$, let $K_m$ denote the complete graph on $m$ vertices. A subdivision $H$ of $K_m$ is obtained by replacing each edge of $K_m$ by a path of positive length, with distinct replacement paths having disjoint interiors and with no original vertex occurring in a path interior. Define the $r$-blow-up $H^{(r)}$ to have vertex set $V(H)\times\{1,\ldots,r\}$, where $(u,i)$ and $(v,j)$ are adjacent exactly when $uv\in E(H)$. Thus each vertex is replaced by an independent set of size $r$, and each edge is replaced by a complete bipartite graph between the corresponding sets. Containment below means containment as a subgraph, without an induced-subgraph requirement.

Under the standard convention that graphs are finite, simple, and undirected, and interpreting the source's $\Omega$-notation as a sufficiently large constant threshold, the proposed statement is: \[ \begin{gathered} \text{For every pair of integers }m,r\geq 2,\text{ there exist }C=C(m,r)>0 \text{ and }n_0=n_0(m,r)\in{\mathbb{N}}\text{ such that}\\ \text{for every integer }n\geq n_0\text{ and every graph }G\text{ with }|V(G)|=n,\\ |E(G)|\geq C n^{\,2-1/r} \quad\Longrightarrow\quad \exists H\text{ a subdivision of }K_m\text{ with }H^{(r)}\subseteq G. \end{gathered} \] The subdivision $H$ may depend on $G$; the source imposes no bound on the lengths of its replacement paths. The graph conventions, the blow-up convention, and the quantification of the implicit density constant are conventional interpretations that require confirmation against the report, since the supplied statement does not explicitly define them. In particular, the displayed formulation does not assert the conclusion for every prescribed positive density constant.

The supplied dated curation labels the problem partially solved and reports a sufficient density threshold with the additional factor $(\log n)^{60/r}$, while describing removal of that factor as open. The original excerpt also calls this bound tight up to that factor, referring to a proposition not included in the supplied record. These are supplied source claims, not independently verified conclusions here.

The original excerpt interleaves a separate Question 6: for fixed $m\geq2$, find the smallest $c$ such that every sufficiently large properly edge-coloured $n$-vertex graph with $\Omega(n(\log n)^c)$ edges contains a rainbow subdivision of $K_m$, and in particular determine whether $c=1$. Proper edge-colouring means that incident edges have distinct colours; rainbow means that all edges of the subdivision have distinct colours. This neighbouring question is context rather than an additional hypothesis of the main statement. The excerpt further describes its question as strengthening Question 6.2 in reference [4], whose bibliographic identity is not supplied.

Short English statement

For each fixed $m,r\geq2$, ask whether a sufficiently large constant multiple of $n^{2-1/r}$ edges forces a graph to contain the $r$-blow-up of some subdivision of $K_m$. The supplied curation reports a result with an extra $(\log n)^{60/r}$ factor and labels its removal open. The precise graph and density-constant conventions require review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004979$, titled Blow-Ups of Clique Subdivisions in Dense Graphs; exact source problem code catalogue entry. The record assigns proposed year 2022 and identifies no individual proposer.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. https://doi.org/10.4171/owr/2022/1. The supplied literature-source label is "Oberwolfach Report 1/2022." The title year and report year differ in the supplied metadata and have not been reconciled here. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Jiang, Letzter, Methuku, and Yepremyan, "rainbow clique subdivisions and blow-ups" (supplied descriptive label). https://arxiv.org/abs/2108.08814. No independent inspection of this reference is claimed.
• Literature assessment checked at 2026-08-22: this is supplied dated curation, not independently verified. It labels the problem partially solved, reports a sufficient threshold with factor $(\log n)^{60/r}$, and describes the threshold without that factor as open. The background explicitly calls this a dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says it was checked against the official report. This is supplied verification metadata, not an independent verification performed for this draft. The original excerpt refers to a proposition and to Question 6.2 in reference [4]; neither that proposition nor the bibliographic entry for [4] is supplied.