Structural Determinants of Graph Ramsey Numbers

Definitions and mathematical statement

The supplied record poses an exploratory question and does not specify a quantitative conjecture. Under the conventional interpretation in which $H$ is a finite simple undirected graph and the Ramsey number is diagonal with two colours, define \[ r(H)=\min\left\{N\in\{1,2,\ldots\}:\text{ every red--blue colouring of }E(K_N)\text{ contains a monochromatic copy of }H\right\}. \] Here $K_N$ is the complete graph on $N$ vertices, and a monochromatic copy means an injective map $f:V(H)\to V(K_N)$ for which all edges corresponding to $E(H)$ have one common colour; the copy need not be induced. These conventions are a possible interpretation and are not explicitly fixed by the supplied source record.

The question, with its original exploratory scope preserved, is: Which structural properties of a graph $H$ approximately determine its Ramsey number?

The record specifies neither the structural parameters to be used nor the meaning of approximation, its permitted error, or a graph family over which a bound should hold uniformly. Consequently, it does not determine a precise quantified estimate. Its background refers to a lower bound, constant-chromatic and bipartite cases, and a claimed order estimate, but supplies no formulas or hypotheses identifying those claims. These references cannot be converted into a mathematical conjecture without further source information.

Short English statement

The problem asks which structural features of a graph control the approximate size of its Ramsey number. The supplied record leaves both the Ramsey-number convention and the required approximation unspecified, so a precise quantitative conjecture remains unresolved.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002463$, exact source problem code catalogue entry, title "Structural Determinants of Graph Ramsey Numbers." The record belongs to the Oberwolfach Reports Open Problems collection, gives proposed year 2014, and identifies no individual proposer.
• Supplied source citation: Combinatorics (2014), Oberwolfach Reports, pp. 5--90, DOI 10.4171/owr/2014/01. Original OWR record: https://doi.org/10.4171/owr/2014/01. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions; no narrower location within the report is supplied.
• Supplied literature source labelled "Conlon Fox Sudakov Ramsey bounds": https://arxiv.org/abs/1002.0045.
• Supplied literature source labelled "Recent Ramsey theory lecture notes": https://www.n.ethz.ch/~ywigderson/math/static/RamseyTheory2024LectureNotes.pdf.
• Literature assessment checked at 2026-08-21, as supplied dated curation, not independently verified: the record labels the problem open and states that the lower bound and the constant-chromatic and bipartite cases are known, while the claimed order estimate remains open for general graphs. The background characterizes this as dated literature triage derived from the supplied OWR curation and calls for independent verification of time-sensitive status and cited claims. The underlying bound and order estimate are not stated in the record.
• The supplied statement status is corrected_verified; its accompanying note reports a manual semantic, typographic, and LaTeX review of a meaning-preserving cleanup. This is supplied editorial provenance, not independent mathematical or source verification of this draft.