Proofs of Lower Bounds for Ramsey Numbers? - MathOverflow

Proofs of Lower Bounds for Ramsey Numbers?

2010-06-24T21:06:55Z

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic argument, given here for example, as well as the following:

(This is a sketch; it's worth working out the details.) Represent a two-coloring of the edges of a complete graph on $n$ vertices as the upper triangle (strictly above the diagonal) of an $n\times n$ matrix of zeroes and ones (that is, ${n\choose 2}$ bits). We may rewrite this representation by noting which vertices are contained in our monochrome subgraph and what color it is, as well as including all the remaining edge data, using some special characters to block off this data. If Ramsey numbers are small, this sends each string of bits under an appropriate encoding to a smaller string of bits, which is impossible by pigeonhole. (I am being purposely vague about the encoding--pick your own, anything goes essentially--because it's a bit boring). The bound this argument gives is essentially the same as the probabilistic one, and indeed it seems to me to be essentially a "derandomization" of that argument.

My question is:

Does anyone know a proof of a similarly good lower bound using a fundamentally different method?

Answer by Matthew Kahle for Proofs of Lower Bounds for Ramsey Numbers?

2010-06-24T21:40:13Z

If I am understanding the jist of your second argument, some might say that it is essentially the same as the first. Pigeonhole principle and probabilistic method both boil down to indirect existance proofs via counting. Although in the Probabilistic Method we can sometimes get away with counting things very roughly or just consider the dominant term in a complicated expression, this is still the spirit.

In fact no one has ever given a true "derandomized" lower bound on Ramsey numbers, at least in the sense of giving any kinds of explicit constructuions, and I think it is fair to say that giving explicit graphs as exponential lower bounds for diagonal Ramsey numbers is considered to be one of the Holy Grails of combinatorics. It took a long time before someone gave superpolynomial deterministic lower bounds (Noga Alon perhaps?), and these bounds are still very far from the exponential bounds one gets from the probabilistic method.

I believe the best lower bounds for diagonal Ramsey numbers come from the Lovasz Local Lemma, but this only reduces your answer by a small factor (perhaps constant factor of 2?). The Local Lemma does better for off-diagonal numbers.

Answer by Ryan Williams for Proofs of Lower Bounds for Ramsey Numbers?

2010-06-24T22:34:35Z

The best known explicit Ramsey graph construction is in the paper:

Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. STOC 2006: 671-680

Call a graph $K$-Ramsey if it doesn't have a $K$-clique or a $K$-independent set. They prove

There is an absolute constant $\alpha > 0$ and an explicit construction of a $2^{2^{\log^{1−\alpha} n}} = 2^{n^{o(1)}}$-Ramsey graph over $2^n$ vertices, for every large enough $n \in {\mathbb N}$.

Here, "explicit construction" means roughly that there is an efficient algorithm which when given the string of $N$ ones, it outputs an $N$-node $K$-Ramsey graph. (I know this is "stronger" than what you would like, but you should still check these things out for fun.)

Before the above paper, the best known explicit construction was by Frankl and Wilson, who showed that there are $2^n$ node graph that are about $2^{\Omega(\sqrt{n})}$-Ramsey. Noga Alon had an alternative construction but I think it only matched Frankl and Wilson. See the above paper for more details.

All these constructions are very neat and use radically different methods from simple counting arguments, so I hope you enjoy them. You may find that the problem of finding a succinct/effective description of a family of lower bound graphs is indeed interesting.