Asymptotic Size-Ramsey Numbers of Paths

Definitions and mathematical statement

Let $P_n$ be the path on $n$ vertices. The supplied statement calls $r_e(H)$ the size-Ramsey number and asks whether, as $n\to\infty$ through the positive integers, \[ \frac{r_e(P_n)}n\longrightarrow\infty, \qquad \frac{r_e(P_n)}{n^2}\longrightarrow0. \] Thus the two requested assertions are superlinear growth and subquadratic growth of the same invariant. Explicitly, the first requires that for every $C>0$ some $N$ satisfy $r_e(P_n)>Cn$ for all $n\ge N$; the second requires that for every $\varepsilon>0$ some $N$ satisfy $r_e(P_n)<\varepsilon n^2$ for all $n\ge N$. The thresholds need not be the same.

In the usual two-color, noninduced convention, a size-Ramsey number would be defined by \[ r_e(H)=\min\{|E(G)|:\text{every red/blue coloring of }E(G) \text{ contains a monochromatic copy of }H\}, \] where $G$ ranges over finite simple graphs. The source does not give the number of colors or define its arrow relation. It also does not say induced, ordered, online, or another variant. These alternatives are materially different, and the asserted superlinear path growth requires particular source scrutiny before the ordinary interpretation and the open label are trusted. This draft does not silently replace the invariant by an induced or online size-Ramsey number.

The exact two limits and the path-on-$n$-vertices convention are retained as source content. No growth theorem or claimed correction is supplied; recovery of the intended Ramsey variant is necessary to establish whether this is a reliable conjectural formulation.

Short English statement

The source proposes growth faster than linear but slower than quadratic for a path size-Ramsey invariant. The two limits are preserved exactly, while the number of colors and the ordinary-versus-induced or other Ramsey convention require verification.

Sources

• Local UnsolvedMath registry, permanent ID 30000603, code catalogue entry, "Asymptotic Size-Ramsey Numbers of Paths." Proposed year 2006; proposer unspecified.
• Combinatorics, Probability and Computing (2007), Oberwolfach Reports, pp. 2875--2952, DOI 10.4171/owr/2006/48; https://doi.org/10.4171/owr/2006/48. The displayed report year 2007 differs from the DOI and proposed year 2006. This is the sole supplied literature reference.
• Statement status corrected_verified; the supplied verification says official-report content was checked and notation, context, and question form normalized without changing the source claim. It does not supply the Ramsey definition omitted here.
• Literature triage checked 2026-08-21: open. It generically describes the claim as an unresolved problem/conjecture/direction and says the supplied targeted check found no authoritative complete resolution. That assessment is not independent verification of the potentially ambiguous path invariant. Created 2026-08-25; updated 2026-09-16.
• Registry curation by Ulam AI / UnsolvedMath Contributors, CC BY 4.0; the underlying report retains its supplied provenance. Unreviewed statement-only draft.