Color Patterns and the Erdős–Rogers Function

Definitions and mathematical statement

Let $k\geq 3$ be a fixed integer, and let $r$ denote the number of colors, interpreted as a positive integer. The supplied record calls $P_r(k)$ a color-pattern parameter and $f_{k,k+1}(r)$ the Erdős--Rogers function. It does not supply definitions of these quantities. In particular, it does not specify the extremal conditions defining $P_r(k)$. Their exact definitions must therefore be recovered from the cited source before this can be a self-contained mathematical statement.

With these symbols retaining their intended source meanings, the extracted conjecture is \[ \text{for every fixed integer }k\geq 3,\qquad P_r(k)=\Theta\!\left(r\,f_{k,k+1}(r)^2\right) \quad\text{as }r\to\infty. \] Explicitly, the intended order-of-growth assertion is that for every integer $k\geq 3$, there exist constants $c_k,C_k>0$ and an integer $r_0(k)\geq 1$ such that every integer $r\geq r_0(k)$ satisfies \[ c_k\,r\,f_{k,k+1}(r)^2 \leq P_r(k) \leq C_k\,r\,f_{k,k+1}(r)^2. \] The constants and threshold may depend on $k$; no uniform assertion for varying $k$ is made. The limit through positive integers is the natural interpretation of the color-count parameter, but the excerpt does not explicitly state the limit or its domain.

The supplied dated curation labels the problem partially solved and says that a construction comes within a logarithmic factor of the conjectured order, while the full asymptotic order remains unproved. This is a supplied literature assessment, not an independently verified conclusion. The excerpt refers to an unspecified Theorem 2 and to improvements of Mubayi and Verstraete, but supplies neither the theorem nor precise bounds; no more specific partial result is asserted here.

Short English statement

For each fixed integer $k\geq 3$, the conjecture asks whether the color-pattern parameter $P_r(k)$ has order $r\,f_{k,k+1}(r)^2$ as the number of colors $r$ grows. The comparison constants may depend on $k$. The supplied record omits the definitions of both parameters, so their precise source conventions require review. Its partially solved label and logarithmic-factor assessment are supplied dated curation.

Sources

• Local UnsolvedMath registry: data/unsolvedmath/problems.json, permanent ID $30006398$, source problem code catalogue entry, title "Color Patterns and the Erdős--Rogers Function." This draft uses the supplied complete registry record.
• Supplied report citation: Combinatorics, Probability and Computing (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/42, pp. 2243--2322. https://doi.org/10.4171/owr/2025/42. The record separately assigns the proposed year 2025; the year discrepancy is unresolved.
• Supplied literature source: "Oberwolfach Report 42 2025." https://oa.tib.eu/renate/bitstreams/72e281a6-ba33-4ac7-baf7-6fadd1126345/download.
• Supplied literature source: Improved Bounds for Minimal Multicolor Ramsey Graphs. https://arxiv.org/abs/2510.09068. The supplied record gives no authors for this reference.
• Literature assessment dated exactly 2026-08-22: the record labels the problem partially solved and describes bounds within a logarithmic factor of the conjectured order. This date and assessment are supplied dated curation, not independently verified source or literature checks.
• Attribution limitations: the excerpt refers to "Conjecture 5.2" without its bibliographic reference, to Mubayi and Verstraete [9], and to constructions of Fox et al. [6], Dudek, Retter, and Rödl [4], Hàn et al. [8], and Bamberg et al. [1]. The numbered bibliography is absent. No individual proposer is identified in the supplied record.