Density Threshold for Rainbow Clique Subdivisions

Definitions and mathematical statement

Fix an integer $m\geq 2$. Under the usual convention that graphs are finite, simple and undirected, let $G=(V,E)$, with $|V|=n$. This graph convention is not explicitly specified in the supplied record and requires confirmation. An edge colouring is a map $\chi:E\to\mathcal C$, where $\mathcal C$ is an arbitrary set of colours. It is proper if distinct edges sharing a vertex have different colours. A subgraph is rainbow if its edges have pairwise distinct colours.

A subdivision of $K_m$ consists of distinct branch vertices $b_1,\ldots,b_m$ and, for every $1\leq i<j\leq m$, a path $P_{ij}$ of positive length joining $b_i$ to $b_j$. These paths have pairwise disjoint interiors, no branch vertex is internal to a path, and distinct paths intersect only at their prescribed common endpoints. The subdivision is rainbow when all edges in the union of these paths have distinct colours. The subdivision need not be induced.

For a real exponent $c$, a customary sufficient-density interpretation of the source's $\Omega$-notation is the property \[ \begin{aligned} \mathcal P_m(c):\quad &\exists C=C(m,c)>0\;\exists n_0=n_0(m,c)\geq 2\;\forall n\in{\mathbb{N}},\ n\geq n_0,\\ &\forall\text{ properly edge-coloured }G\text{ on }n\text{ vertices},\\ &\qquad |E(G)|\geq Cn(\log n)^c \ \Longrightarrow\ G\text{ contains a rainbow subdivision of }K_m. \end{aligned} \] Here $\log$ denotes the natural logarithm. This quantified interpretation allows the density constant and the sufficiently-large threshold to depend on the fixed parameters, but not on the graph or its colouring. The supplied source does not explicitly settle this constant convention.

Question (source Question 6). For each fixed integer $m\geq 2$, what is the smallest admissible exponent $c$ for which $\mathcal P_m(c)$ holds? In particular, does $\mathcal P_m(1)$ hold? The permitted domain of exponents is not specified in the source; using real exponents above is an explicit interpretation. The existence of a smallest exponent, rather than merely an infimum, is part of the unresolved formulation. The stated range $m\geq 2$ is retained without imposing an unstated restriction to larger cliques.

The supplied historical excerpt reports an upper exponent $c\leq 60$. The supplied curation dated 2026-08-22 reports an upper density scale $n(\log n)^{1+o(1)}$, a lower scale $n\log n$, and unresolved questions about the smallest exponent and $c=1$. These are supplied literature assessments, not independently verified conclusions. Their precise parameter ranges and constant conventions are not provided; in particular, they should not be read as uniform assertions for every $m\geq 2$.

Short English statement

For each fixed $m\geq 2$, determine the least logarithmic exponent in a sufficient edge-density bound forcing a rainbow subdivision of $K_m$ in every sufficiently large properly edge-coloured graph. In particular, determine whether a bound $Cn\log n$, with an appropriate constant depending on $m$, suffices. The graph convention, exponent domain, density-constant quantifiers and scope of the supplied literature bounds require review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004977$, source code catalogue entry, title: Density Threshold for Rainbow Clique Subdivisions. Registry location: data/unsolvedmath/problems.json; the project also designates catalog/problems.json for additional existing records. No proposer is named in the supplied record.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78, source Question 6. https://doi.org/10.4171/owr/2022/1. The supplied proposed year is 2022; the report title year and DOI year differ and have not been reconciled here.
• Kuang and Wang, "nearly tight rainbow clique subdivisions" (supplied reference label). https://arxiv.org/abs/2602.08390.
• Jiang, Methuku, and Yepremyan, "rainbow Turán number of clique subdivisions" (supplied reference label). https://doi.org/10.1016/j.ejc.2022.103675.
• Literature assessment checked at 2026-08-22: supplied dated curation, not independently verified. Its supplied status is partially solved; it reports upper scale $n(\log n)^{1+o(1)}$, lower scale $n\log n$, and unresolved optimal-exponent and $c=1$ questions. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and states that it was checked against the official Oberwolfach report. This is supplied verification metadata; no source visit or independent verification is claimed in this draft.