2.1 A critical graph contains the needed core

[a] Lemma 1. Every Ramsey-critical \((k,s)\)-graph contains a

\(K_{k-1}\).

Proof. Let \(r=R(k-1,s)\), and take a \((k-1,s)\)-graph on \(r-1\)

vertices. Adding one universal vertex produces a \((k,s)\)-graph on \(r\)

vertices, so

A critical \((k,s)\)-graph therefore has \(R(k,s)-1\geq r\) vertices. If it

contained no \(K_{k-1}\), it would itself be a \((k-1,s)\)-graph on at least

\(r\) vertices, contradicting the definition of \(r\). \(\square\)

2.2 Explicit gadget

Fix \(k\geq5\). Let \(G\) be any \((k,s)\)-graph containing a labelled clique

Write all of \(V(G)\) as \(U\), and create two new sets

Define \(F\) as follows.

1. Keep \(G\) on \(U\), and make \(V\) a \(K_{k-1}\).

2. Split \(W\) into

\[ W_1=\{w_0,w_1\},\qquad W_2=\{w_2,\ldots,w_{k-2}\}. \]

Make each \(W_i\) a clique and put no edges between \(W_1\) and \(W_2\).

3. The only \(U\)-to-\(V\) edges are the matching edges \(u_iv_i\).

4. Join \(w_i\) to \(u_j\) precisely when

\(i\ne j\) and \(u_iu_j\in E(G)\).

5. Join \(w_i\) to \(v_j\) precisely when \(i\ne j\).

This is exactly the \(t=2\), \(H=M=K_{k-1}\) specialisation of the 2011

construction, written without invoking its general notation.

2.3 Clique check

[a] Lemma 2. \(F\) contains no \(K_k\).

Proof.

Suppose a clique \(Q\) meets both \(U\) and \(V\). The only edges between

these sets form a matching, so

for one \(i\). Since there are no \(W_1\)-to-\(W_2\) edges, the rest of

\(Q\) lies in one \(W_j\). Every \(w_h\) in it must have \(h\ne i\).

For \(k\geq5\),

and hence \(|Q|\leq2+(k-3)=k-1\).

If \(Q\) does not meet both \(U\) and \(V\), replace every \(w_i\in Q\) by

the corresponding \(u_i\) (on the \(U\) side) or \(v_i\) (on the \(V\)

side). The replacement is injective because \(w_i\) is adjacent to neither

\(u_i\) nor \(v_i\), and the defining mirrored adjacencies make the image a

clique of the same size in \(G\) or \(K_{k-1}\). Its size is therefore at

most \(k-1\). \(\square\)

2.4 Independence check

[a] Lemma 3. If \(\alpha(G)\leq s-1\), then \(\alpha(F)\leq s\).

Proof.

Let \(I\) be independent in \(F\), with parts \(I_U,I_V,I_1,I_2\) in

\(U,V,W_1,W_2\). For \(r=1,2\), let \(C_r\) be the selected \(U\)- or

\(V\)-vertices whose corresponding \(w_i\) lies in \(I_r\).

Partition \(I\) into

Map \(A\) injectively into \(G\) by sending every indexed \(w_i,u_i,v_i\)

to \(u_i\), and leaving the unindexed \(U\)-vertices where they are.

Injectivity follows because \(w_i\) is adjacent to neither corresponding

copy, while \(u_i v_i\) is a matching edge. The mirrored-edge rule makes

the image independent; when a selected \(v_i\in C_2\) is mapped to \(u_i\),

the simultaneously selected \(w_i\in I_2\) certifies all required

nonadjacencies to the other mapped vertices. Thus

Similarly, map \(B\) into the complete graph on \(V\), sending its indexed

vertices to \(v_i\). Its image is independent, so \(|B|\leq1\). The two

sets partition \(I\), whence \(|I|\leq s\). \(\square\)

2.5 Ramsey consequence

[a] Theorem 4. For \(k\geq5\) and \(s\geq2\),

Proof.

Take a critical \((k,s)\)-graph \(G\) on \(R(k,s)-1\) vertices. Lemma 1

supplies the \(K_{k-1}\) core. The construction adds \(2(k-1)\) vertices,

and Lemmas 2--3 show that the resulting

vertex graph is a \((k,s+1)\)-graph. Add one to its order to obtain the

Ramsey lower bound. \(\square\)

Taking \(s=k\) and \(R(k,k+1)=R(k+1,k)\) proves

3. Exact ceiling of this construction family

[a] Proposition 5. The increment \(2k-2\) is optimal among all

applications of Xu--Shao--Radziszowski Theorem 3 which start with a critical

\((k,s)\)-graph and target \((k,s+1)\).

Proof.

That theorem combines a \((k,s)\)-graph \(G\), a \((k,t)\)-graph \(H\), and

a common induced graph \(M\), and targets the second parameter \(s+t-1\).

To obtain \(s+1\), necessarily

Since \(\alpha(H)<2\), \(H\) is complete. Since \(\omega(H)

\(h\) satisfies \(h\leq k-1\). The common induced graph has order

\(m\leq h\leq k-1\).

Starting with the largest possible seed, of order \(R(k,s)-1\), the theorem

therefore adds at most

to the resulting Ramsey lower bound. Equality is attained by

\(H=M=K_{k-1}\), exactly as in Section 2. \(\square\)

The relative-gain wall

[a] A random red/blue coloring of \(K_n\) has expected number of

monochromatic \(K_k\)'s

For \(n=\lfloor2^{k/2}\rfloor\),

Thus

Consequently the largest relative increment certified by the entire

construction family in Proposition 5 obeys

This is an exact obstruction to that method, not evidence that the true

ratio tends to one.

4. A non-additive true-twin packing reduction

The preceding construction is forced to add only \(O(k)\) vertices. There

is a different, genuinely non-additive route which turns the missing step

into a concrete packing problem.

Let \(G\) be a \((k,k)\)-graph and let \(S\subseteq V(G)\). Form \(G^S\) by

replacing every vertex in \(S\) by a two-vertex clique of true twins, every

other vertex by a singleton, and putting a complete or empty bipartite graph

between two fibres according as their original vertices are adjacent or

nonadjacent in \(G\).

[a] Proposition 6 (exact blow-up formulas).

and

Proof.

An independent set uses at most one vertex from each clique fibre, and its

projection is independent in \(G\); conversely every independent set of

\(G\) lifts by choosing one representative per fibre. A clique projects to

a clique \(C\) of \(G\), and it may use both vertices precisely in the

fibres indexed by \(C\cap S\). Taking all allowed fibre vertices attains

the displayed maximum. \(\square\)

It follows that \(G^S\) is a \((k+1,k)\)-graph exactly when

The constraint is automatic for \(|C|\leq\lfloor k/2\rfloor\), so (TP) is

a finite 0--1 packing problem involving only the larger cliques of \(G\).

[a, fractional diagnostic] In the linear-programming relaxation of

(TP), the uniform assignment

is always feasible. Indeed, for a clique of order \(r\leq k-1\),

It has fractional value \(|V(G)|/(k-1)\). Thus even a constant-factor

rounding theorem for this particular clique-capacity system would give an

integral packing of exponential-over-polynomial order and would already

prove the still-open

\((R(k+1,k)-R(k,k))/k\to\infty\). The possible integrality gap is therefore

a precise obstruction; this observation does not supply the rounding

theorem or the constant-density packing needed for #1030.

[a] Corollary 7.

If \(G\) is Ramsey-critical for \((k,k)\) and \(S\) satisfies (TP), then

In particular, sets satisfying

for some fixed \(\varepsilon>0\) and all large \(k\) would prove the

corresponding liminf separation in #1030.

Proof.

The blow-up has

has independence number at most \(k-1\), and has clique number at most

\(k\) by (TP). It is therefore a lower-bound witness for \(R(k+1,k)\).

[a, exact obstruction inside this ansatz] If every edge of \(G\) lies

in a \(K_{k-1}\), then (TP) forces \(S\) to be independent: a

\(K_{k-1}\) may contain at most one selected vertex. Hence

Thus this route needs a diagonal critical graph with a positive-density

packing which evades the capacities of all its large cliques. No theorem

found in the audit supplies such a graph or packing. This is a sufficient

reduction, not an assertion that every possible solution must have this

form, and it still does not establish existence of the literal limit.

[d] As finite sanity checks, the standalone program solves (TP) by

complete enumeration for the \(C_5\) diagonal witness at \(k=3\) and the

Paley-17 diagonal witness at \(k=4\). Their optimum packing sizes are 2 and

3, respectively; the corresponding true-twin blow-ups have

\((\omega,\alpha)=(3,2)\) on 7 vertices and \((4,3)\) on 20 vertices. These

small values are checks of the reduction, not asymptotic evidence.

5. Exact initial cases

| \(k\) | \(R(k,k)\) | \(R(k+1,k)\) | ratio | status |

|---:|---:|---:|---:|:---|

| 2 | 2 | 3 | \(3/2\) | [a] |

| 3 | 6 | 9 | \(3/2\) | [a] |

| 4 | 18 | 25 | \(25/18\) | [a] denominator; [b] numerator |

[a] \(R(q,2)=q\) directly from the definition.

[a] The checker exhausts all \(2^{15}=32768\) labelled graphs on six

vertices, finds no \((3,3;6)\)-graph, and finds exactly 12 labelled

\((3,3;5)\)-graphs (the labelled 5-cycles). Hence \(R(3,3)=6\).

[a] The complement of the eight-vertex Möbius ladder has

\((\omega,\alpha)=(3,2)\), proving \(R(4,3)>8\). In a hypothetical

\((4,3;9)\)-graph, every vertex has degree at most five because its

neighborhood is a \((3,3)\)-graph. Its antineighborhood is a clique of

order at most three, so every degree is also at least five. All nine

degrees would equal five, contradicting the handshake lemma. Thus

\(R(4,3)=9\).

[a] The Paley graph on \(\mathbb F_{17}\) has

\((\omega,\alpha)=(3,3)\), checked from its quadratic-residue definition,

so \(R(4,4)>17\). In a hypothetical \((4,4;18)\)-graph, a vertex

neighborhood has at most \(R(3,4)-1=8\) vertices, and its antineighborhood

has at most \(R(4,3)-1=8\). These two sets would have to contain all 17

other vertices, a contradiction. Hence \(R(4,4)=18\).

[b] T. Gauthier and C. E. Brown,

A Formal Proof of \(R(4,5)=25\),

DOI 10.4230/LIPIcs.ITP.2024.16,

arXiv:2404.01761, formally verify

\(R(4,5)=25\) in HOL4. The standalone checker imports their published

24-by-24 witness matrix from the accompanying repository and independently

recomputes \((\omega,\alpha)=(3,4)\), proving the lower side

\(R(4,5)>24\). The upper side remains explicitly modulo their named formal

theorem.

No uniform conclusion may be drawn from three exact ratios.

6. Standalone verifier

The self-contained standard-library program is

erdos1030_wave6s_reverify.py. It implements

its own bitset maximum-clique search and separately cross-checks the finite

witnesses by direct subset enumeration; no SAT package, graph package, or

download is trusted at run time.

Run from the repository root:

python runs/erdos1030_wave6s_reverify.py

Observed output:

R(3,3)=6: exhaustive labelled-graph check passed
R(4,3)=9 and R(4,4)=18: witnesses and elementary reductions passed
R(4,5)>24: explicit 24-vertex witness has (omega,alpha)=(3,4)
R(4,5)<=25: EXTERNAL HOL4 theorem; not recomputed by this script
XSR K_{k-1}-seed checks (k,n,omega,alpha): [(5, 12, 4, 2), (6, 15, 5, 2), (7, 18, 6, 2), (8, 21, 7, 2), (9, 24, 8, 2), (10, 27, 9, 2), (11, 30, 10, 2), (12, 33, 11, 2)]
XSR exhaustive fixed-K4/two-extra stress tests passed: 446
True-twin checks (seed,n,packing,omega,alpha): [('C5', 5, 2, 3, 2), ('Paley17', 17, 3, 4, 3)]
Adjacent XSR ceiling max(h+m)=2k-2 verified for 5<=k<=100
Random-colouring denominator and vanishing-relative-gain arithmetic passed
ALL CHECKS PASSED

The 446 stress tests are all admissible labelled graphs formed from a fixed

\(K_4\) and two extra vertices; the other 66 of the \(2^9=512\) possibilities

contain a \(K_5\) and correctly fail the seed hypothesis.

7. Precise remaining wall and compute cost

Define the exact extremal quantities

Then the displayed ratio is exactly

[a] The construction above proves only

To obtain a fixed multiplicative gap, the missing mathematical input is a

uniform theorem of the scale

for some \(\varepsilon>0\). To meet the live statement literally, one must

also prove that \((M_k+1)/(N_k+1)\) has a limit. No construction or theorem

found in the literature audit supplies either ingredient.

[d, cost evidence] A raw SAT encoding of just \(R(4,4)\leq18\) did not

finish in a deliberately capped 180-second local trial; I discarded it

rather than treating solver silence as evidence. The elementary reduction

in Section 5 is the actual certificate.

[d, published reproducibility cost] Even the finite theorem

\(R(4,5)=25\) is substantial. Gauthier--Brown report running the final

formal gluing phase on four 512--1024 GB machines, 40 cores per machine, for

under nine days, and producing roughly a petabyte of proof files. The time

ceiling is about

At an illustrative \(0.05\)--\(0.10\) USD per core-hour this is

\(\$1.7\)k--\(\$3.5\)k for CPU alone; suitable high-memory instances and

petabyte-scale storage would dominate that estimate. Replaying it is far

beyond this VM and would not address the asymptotic problem.

[a, asymptotic cost diagnosis] Since already

\(R(k,k)>2^{k/2}\), brute-force enumeration at the relevant order has at

least

edge colorings. Thus finite enumeration cannot provide the required

uniformity step. The exact missing object is a non-additive construction or

structural lemma giving \(\Omega(N_k)\), rather than \(O(k)\), new vertices

while increasing the permitted clique size by only one and leaving the

independence threshold fixed.

PARTIAL: verified the omitted stronger linear bound \(R(k+1,k)-R(k,k)\geq2k-2\) for \(k\geq5\), proved its optimality within the Xu--Shao--Radziszowski adjacent construction family, and reduced a proportional gap to an explicit true-twin clique-packing lemma whose uniform and limit-existence steps remain open.