Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large monochromatic subgraphs?
That is, can we explicitly construct (edge) 2-colourings on graphs of size $c^k$, for some $c>0$, with no monochromatic complete subgraph of size $k$?
I believe the answer is "no"; the best known constructions only give no clique or independent set of size about $2^\sqrt{n}$ in a graph with $2^n$ vertices. Bill Gasarch has a page on the subject here, although I don't know how frequently it updates.
Finding explicit constructions for Ramsey graphs is a central problem in extremal combinatorics. Indeed, computational complexity gives a way to formalize this problem. Asking for a graph which can be constructed in polynomial time is a fairly good definition although sometimes the definition is taken as having a log-space construction.
Until quite recently the best method for explicit construction was based on extremal combinatorics. The vertices of the graphs were certain sets (say k-subset of an n element sets) and the edges represented pairs of sets with presecibed intersection. The best result was by Frankl and Wilson and it gives a graph with n vertices whose edges are colored by 2 colors with no monochromatic clique of size $\exp (\sqrt{(\log n))}$. (I think this translates to $k^{\log k}$ in the way the question was formulated here.) Using sum-products theorems Barak Rao Shaltiel and Wigderson improved the bound to $\exp (\log n^{o(1)})$.
Payley graphs are conjectured be explicit examples for the correct behavior. But proving it is much beyond reach.
Update(Nov 11, 2015): Gil Cohen found an explicit construction with no monochromatic cliques of size $2^{(\log \log n)^L}$. An independent construction which applies also to the bipartite case was achieved by Eshan Chattopadhyay and David Zuckerman
I also believe the answer is "no". Another reference is this paper, which treats off-diagonal Ramsey numbers (e.g. graphs with no clique of size k and no anti-clique of size l).
As was mentioned in the previous answers, the answer is no. Or more accurately I'd say that the answer is currently no, but possibly yes.
Also, consider the related question of constructing a bipartite graph with parts of size $2^n$, which contains no $K_{k,k}$ and whose complement contains no $K_{k,k}$ where $k = O(n)$. Such an explicit construction will have as far as I can tell huge impact on derandomization of randomized algorithms, among other topics in theoretical computer science. See e.g. this paper, where such an explicit construction is given for $k = 2^{n^{o(1)}}$.
You might also be interested in the following accompanying paper (seems like I cannot post it, being a new user; you can google it though, its title is "Pseudorandomness and Combinatorial Constructions") to Luca Trvisan's talk at ICM '06. This may contain more connections between explicit constructions of combinatorial objects and applications in theoretical computer science.
A question I have here is what do you mean by "explicit"?
Personally, I like the definition that a construction is explicit if it can be constructed in polynomial time (due to Alon? Wigderson??). Given that we are talking about exponentials in n here, this gets (slightly) complicated, but we'll say the controlling parameter here is $N=2^n$, the rough order of the number of vertices in a possible Ramsey graph.
One conjecture I have is that the set of Paley graphs on p vertices, where p ranges over all primes $1 \mod 4$ between $2^{(n/2)}$ and $2^{(n-1)}$ gives a lower bound on $R(n)$. This is NOT an explicit set, by my definition above. ::::grin:::::
If memory serves me, I think the best result known for your original question is in a paper of Noga Alon from a few yrs back. You may want to check his web page as well as Gasartch's survey page mentioned before.
I just saw this. Actually there is a constructive solution to the original Ramsey number lower bound. One can define an energy function which counts the number of mono-chromatics and try to minimize it. The probabilistic lower bound follows from a mean-value theorem and the method is constructive, see
https://mathoverflow.net/q/210813
The method is also generic, for a general SAT instance in disjunctive normal form one can write down a similar energy function which counts the number of falsified clauses, which has the same sum-product form.
So it applies to problems in NP. This is not surprising if we recall Ramsey proved his what we now called "Ramsey theorem" when trying to solve the decision problem for first order logic (the general problem is later shown to be undecidable).
