As a sort of dual question to thisthis 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?
