Order-robust ordered Ramsey numbers of regular graphs

Definitions and mathematical statement

For a graph $H$ with a linear vertex ordering $\prec$, let $r_<((H,\prec))$ be the least $N$ for which every red/blue coloring of the ordered complete graph on $[N]$ contains an order-preserving monochromatic copy of $H$. The copy is not required to be induced.

Primary ordered-Ramsey question. Is there $c>0$ such that, for every sufficiently large $n$, some $100$-regular graph $H$ on $n$ vertices satisfies \[ r_<((H,\prec))\geq n^{1+c}\qquad\text{for every ordering }\prec? \] The graph must be chosen before the universal quantifier over its orderings.

Supplied affirmative answer. The aid credits Balko--Jelinek--Valtr with proving that almost every fixed-degree $d$-regular graph obeys, simultaneously for all orderings, \[ r_<((H,\prec))\geq\frac{n^{3/2-1/d}}{4\log n\log\log n}. \] This is interpreted for sufficiently large admissible $n$ with $dn$ even; the theorem's precise fixed-degree range and citation are not supplied. At $d=100$, the exponent is $149/100$, and every fixed $0<c<49/100$ works after absorbing the logarithmic denominator. In particular $c=12/25$ answers the source question; even degree $100$ imposes no parity restriction on $n$.

Reported regular completion. If integers $0\leq d\leq D$ satisfy $D-d$ even and \[ n\geq\max\{D+2,2d+2\}, \] the aid proves that every $d$-regular $n$-vertex graph $G$ has a spanning $D$-regular supergraph $H$. Edge containment gives the order-robust monotonicity \[ \min_\prec r_<((H,\prec))\geq\min_\prec r_<((G,\prec)). \] Thus robust degree-four examples lift to degree $100$ on the same vertex set for $n\geq102$. This is a transfer lemma, separate from the supplied literature proof of existence.

Appended different section: Ramsey meets Erdős--Szekeres. The canonical record continues across a section boundary and names Dhruv Mubayi. It defines $g(s,n)$ to be the minimum $N$ such that every $N$ planar points in general position (conventionally no three collinear), with all pairs colored red/blue, contain either $s$ points in convex position with every pair red or $n$ such points with every pair blue. The source prints the historical bounds \[ 4^n<g(n,n)<2^{O(n^2\log n)}, \] \[ 2^{n-1}<g(s,n)<r(4^s,4^n)<(4^n)^{4^s}. \] Their exact asymptotic ranges and lower-bound conventions are not given. In particular the displayed $4^n$ lower bound cannot be read literally for every small $n$ (for triangles, $g(3,3)=6$), so it requires source verification rather than silent correction. No result in the attached research summary addresses this appended geometric-Ramsey section. The solved status concerns the primary order-robust regular-graph question, not a resolution of all geometric-Ramsey bounds.

Short English statement

The aid reports an affirmative answer for one $100$-regular graph whose ordered Ramsey lower bound holds under every ordering, and gives a same-vertex regular-completion transfer. The source also accidentally continues into a separate convex-position Ramsey section; its definition and qualified historical bounds are retained without assigning it the primary question's solved status.

Sources

• Local UnsolvedMath registry, permanent ID $20000954$, catalogue entry; canonical aim-combinatorics-notes.json, notes[78].
• AIM workshop "Graph Ramsey theory," "Ordered Ramsey numbers," item 32, followed by "Ramsey meets Erdős--Szekeres" with heading attribution Dhruv Mubayi: https://www.overleaf.com/read/mnvcscjjysvg.
• Balko--Jelinek--Valtr all-orderings regular-graph theorem, as named in the attached summary; no full title, identifier, year or precise theorem range supplied.
• Research attempt 1, full_solution, run status solved, internal rigor proved, low novelty confidence; registry SOLVED-IN-LITERATURE. Explicitly machine-generated, not peer reviewed, and to be independently verified before citation. Original literature field empty.