13
$\begingroup$

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 :)

$\endgroup$
5
  • $\begingroup$ Interesting question. For a moment I thought I might have an answer but I was making an idiotic mistake. Will think about it. $\endgroup$
    – gowers
    Jan 29, 2011 at 10:21
  • $\begingroup$ Is anything known about how many monochromatic $K_{n-1}$ there are in a $K_n$-free edge colouring of $K_{R(n,n)-1}$? $\endgroup$ Jan 30, 2011 at 0:05
  • $\begingroup$ @Anthony Quas: If I remember correctly, the keyword to search on is "Ramsey multiplicity," but I suspect very little is known. $\endgroup$ Jan 30, 2011 at 2:56
  • $\begingroup$ @Anthony, @Daniel, this question mathoverflow.net/questions/26040/ramsey-multiplicity almost precisely addresses the question of Anthony. The answer, essentially, is that nothing is known. This also puts the kibosh on Anthony's proof technique, unfortunately, which is too bad because it's hard to see how to do anything except for what Anthony suggests. Incidentally, in the other thread I link, the difference R(n,n+1)-R(n,n) comes up. $\endgroup$ Jan 30, 2011 at 14:04
  • $\begingroup$ @Louigi: Very nice and thorough answer you gave. Too bad the extension technique can't be used :( $\endgroup$ Jan 30, 2011 at 19:36

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ Am I being silly? This doesn't seem to work at all--namely adding $100n$ new vertices shows that the lim inf tends to something $\geq 100$, not infinity. But yes, I'd believe some variant of this works. In particular, adding $n-1$ new vertices, such that all the old-new edges are blue, and all the new-new edges are red, works, and shows that the lim inf tends to something $\geq 1$. $\endgroup$ Jan 30, 2011 at 8:48
  • $\begingroup$ 100 was meant to be code for something that could be taken arbitrarily large as $n$ goes to infinity... $\endgroup$ Jan 30, 2011 at 14:16
  • $\begingroup$ Ah, I see. Sorry about that. $\endgroup$ Jan 30, 2011 at 19:19
0
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ I think you don't want that $O(n)$ there, it means the left side is less than a constant times $n$, which hasn't been proved and wouldn't be helpful if it had been. $\endgroup$ Sep 24, 2010 at 12:49
  • $\begingroup$ Yes what I wrote was completely rubbish, sorry. $\endgroup$
    – alext87
    Sep 24, 2010 at 13:47
  • $\begingroup$ That is ok thanks for trying. How do I remove the answered distinction? $\endgroup$
    – Orange
    Sep 24, 2010 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.