Differences of near diagonal Ramsey numbers. - MathOverflow

Differences of near diagonal Ramsey numbers.

2010-09-24T05:12:16Z

I am a graduate student trying to get involved in Ramsey theory. My question comes from:

Erdős on graphs: his legacy of unsolved problems By Fan R. K. Chung, Paul Erdős, Ronald L. Graham

p.14 of this book is available as a google ebook.

They quote Erdos in a 1980/1981 paper

"Faudree, Shelp, Rousseau, and I needed recently a lemma stating:

(R(n+1,n)-R(n,n))/n --> infinity as n--> infinity. We could prove this without much difficulty."

My first question is how does one show this?? I have tried my hand at this using recursive formulas for bounds on ramsey numbers, but it seems the lower bounds of this type are particularly weak. Furthermore any proof of this is absent from the literature to my knowledge. Any insight will be very very much appreciated.

Also which is larger R(k,k-2)+1 or R(k-1,k-1)? Of course the second but can we prove it?

Also for m+n=r+s=v with m < r =< v/2 =< s < n can we prove R(r,s) >= R(m,n) ?

Bounty to the best response :)

Answer by alext87 for Differences of near diagonal Ramsey numbers.

2010-09-24T08:19:30Z

Maybe try to add $O(n^2)$ vertices to the graph $K_{R(n,n)}$ which is R/B coloured without a blue $K_n$ without creating a $K_{n+1}$ in red.

Answer by Louigi Addario-Berry for Differences of near diagonal Ramsey numbers.

2010-10-20T13:02:06Z

Edit: Erdős got three things wrong. First of all, it wasn't Faudree, Shelp, and Rousseau, it was Faudree, Shelp, and Burr. Second, it wasn't "recently", it was in the future (with respect to the quote you provide)! Third, they didn't prove that $(R(n+1,n)-R(n,n))/n \to \infty$, but only that $R(n+1,n)-R(n,n) \geq 2n-3$.

The relevant paper is On the difference between consecutive Ramsey Numbers, published in 1989. The proof is not long. On a (somewhat cursory) search I wasn't able to find any papers citing this one that address the same question, so it seems likely that this bound is still the best known.

Old answer.

For your first question: thanks to Miklos Simonovits and others, all of Erdős' papers are available from this site. I scanned through the papers by Erdős, Faudree, Rousseau and Schelp from up to 1982 but didn't see such a result. There are 12 papers with precisely these four coauthors, and another several that also have Burr as a coauthor, so it may take some time to find (especially if it isn't explicitly stated as a lemma but is embedded in a proof somewhere). But: if they published it, then you'll be able to find your result by scanning through the papers on that site.

Answer by Anthony Quas for Differences of near diagonal Ramsey numbers.

2011-01-30T07:46:59Z

I have a strategy I would want to use, but would need to know something about the $(n-1)$-cliques that show up when you have a colouring avoiding $n$-cliques to make it work

Start off with a 2-edge colouring of $K_{R(n,n)-1}$ avoiding $n$-cliques. Add $100n$ new vertices. Colour the edges between old and new at random with P(red)=$p_1$, small; Colour the edges between the new vertices randomly with P(blue)=$p_2$, small (so that the old-new edges are mostly blue; the new-new edges are mostly red).

You want to avoid a blue $K_{n+1}$ and a red $K_n$. There is basically one way to get a blue $K_{n+1}$: start from a previously existing blue $K_{n-1}$ and find two new points connected by a blue edge such that all edges connecting to the existing $K_{n-1}$ are blue.

There are essentially 2 ways to get a red $K_n$: by finding an existing red $K_{n-1}$ and a new point such that all of the edges connecting the new point to the existing $K_{n-1}$ are red; or by finding a red $K_n$ amongst the newly added vertices.

Let $R$ denote the number of red $n-1$-cliques in the original stuff; let $B$ denote the number of blue $n-1$-cliques.

The expected number of red $n$-cliques of the first type is $100Rnp_1^{n-1}$.

The expected number of red $n$-cliques of the second type is $\binom{100n}{n}(1-p_2)^{n(n-1)/2}$. This is something like $(100e)^ne^{-p_2n^2/2}$ so to make this small you need $p_2=\omega(1/n)$.

The expected number of blue $n+1$-cliques of the type described above is $5000Bn(n-1)(1-p_1)^{2(n-1)}p_2$

If you know something about $B$ and $R$ and can make the sum of these quantities less than 1 by a smart choice of $p_1$ and $p_2$ you'd be in business (e.g. if $B$ and $R$ were known to be $o(2^n)$, you can take $p_1=p_2=1/2$ and everything is small)