I am aiming for a "big list" of theorems using probability techniques to prove existence of some objects. And in each case, there is an interesting question — can we find an explicit example? Was the probabilistic method the first one to come by or it was following the explicit construction? Are there any examples where it is proven that the example exists but its explicit construction is impossible?
In wikipedia, on Probabilistic method, they do propose two examples due to Erdős:
FIRST ONE. For a complete graph on n vertices it is possible to color the edges of the graph in two colors so that there is no complete subgraph on r vertices which is monochromatic (every edge colored the same color).
Question: is there any explicit algorithm for such a coloring?
SECOND ONE. The second problem also comes from graph theory and deals with a chromatic number of a graph: the minimal number of colors in which we can color the graph so that two adjacent vertices are colored differently. Given two positive integers $g$ and $k$, does there exist a graph containing only cycles of length at least $g$ such that its chromatic number of is at least $k$? It can be shown by the means of probabilistic method that such a graph exists for any values of $g$ and $k$.
Question: is there some algorithm to provide such a coloring?
I am not at all a specialist in graph theory, so I would like to hear the answers to thse questions as well as to see other examples which come from other branches of math.
Best Answer
I am a bit surprised that no one has so far mentioned expanders, for which the existence result was first established by the "probabilistic method" in a very simple way, whereas concrete examples of expanders are always a pretty difficult problem, see, for instance, Who first dubbed them "expander graphs"? or How to prove a random d-regular graph is an expander with prob >= 0.5?