What is an explicit Construction?

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to construct it! An early example was lower bounds on the Ramsey Numbers: You can prove that there exists a 2-coloring of the edges of K_n with no monochromatic k-cliques where n=2^k/2, and the proof does not give a way to construct the coloring! When Joel Spencer wrote his first book on The Probabilistic Method (appeared in 1974) this kind of argument was still considered novel. Now they are quite common. Such arguments were (and still are) called Nonconstructive. However, at the time, the term was not defined rigorously.

Of course, once you know that such a coloring exists, it is easy to find one by just looking at all possibly colorings. Hence this use of nonconstructive proofs would not be an issue for logicians.

Many of the early prob method arguments actually showed that most colorings have the property you want. Hence they would lead to randomized polynomial time algorithms. With this in mind, here is one possible definition that seems to cover what Erdos and company were thinking informally:

Definition: A coloring of an object X is constructive if it can be obtained in time polynomial in the size of X.

Is this a good definition? Now that we think P=BPP, or at least that BPP is a good notion of feasible, perhaps we should call randomized algorithms constructive. Moser and Tardos think so since there paper entitled A constructive proof of the General Lovasz Local Lemma has a randomized algorithm.

Here is a history of the prob method as applied to lower bounds on VDW numbers (see here for definitions and some of the proofs). Let W(k) be the least number such that, no matter how you 2-color {1,...,W(k)}, there will be a monochromatic arithmetic sequence of length k.

1. W(k) &ge sqrt(k)2^(k-1)/2 is an easy application of the Prob Method. The proof is so easy that I could not find it written down anywhere, so I wrote it down in the paper pointed to above.
2. W(k) &ge sqrt(k)2^(k-1)/2 can be proved constructively by the method of conditional expectations. This is also so easy that I could not find it written down anywhere. So I wrote it down myself in the paper pointed to above.
3. Berlekamp showed that, if p is prime, then W(p) &ge p2^p constructively. (I prove a slightly weaker result in the paper linked to above.) (Berlekamp's original paper can be found on my website of VDW papers: here.)
4. Using the Local Lovasz Lemma one can show that W(p)&ge 2^k/ek. This proof is nonconstructive and does not yield and almost-all result, so it cannot be turned into a randomized algorithm.
5. Moser and Tardos (above link) (and later Beigel with a different proof) showed that the LLL can always be made to yield a prob algorithm. Hence they have a randomized algorithm to obtain a 2-coloring of {1,...,2^k/ek} with no mono k-AP's. This is not a constructive algorithm in the way that Erdos or Spencer might accept, though it does yield a feasible algorithm.
6. Chandrasekaran, Goyal, Haeupler in the paper Deterministic algorithms for the Lovasz Local Lemma have a deterministic version of the LLL with slightly worse bounds. From their paper one can obtain: W(k) &ge 2^{k/(1+&epsilon)} via a poly algorithm.