Probabilistic method used to prove existence theorems

Question

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.

Answer 1

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?

Answer 2

Shannon's proof that capacity-achieving code families exist for noisy channels is probabilistic in nature. Only for relatively simple channels (e.g., the binary erasure channel, or more recently the binary symmetric channel--and perhaps more generic discrete memoryless channels if I take some abstracts in the recent literature at face value) have explicit code families been given, viz. LDPC and polar codes, respectively.

Answer 3

Problem: given points $x_1, \ldots, x_n$ in $\mathbb{R}^d$ with $n << d$ and $0 < \epsilon < 1$, find a linear map $T \colon \mathbb{R}^d \to \mathbb{R}^k$, $k << d$, such that $$(1 - \epsilon) ||x_i - x_j|| \leq T(x_i) - T(x_j) \leq (1 + \epsilon) ||x_i - x_j||$$

Solution: for $k > C \frac{\log n}{\epsilon^2}$, a random $d \times k$ matrix has the desired property with high probability (where "random" and "high probability" can be made precise).

This is the Johnson-Lindenstrauss lemma - informally, it says that a small amount of high dimensional data can be projected down to a low dimensional space via a suitable random matrix without disturbing the Euclidean distances too badly. This is often used in practice to apply algorithms whose running time is exponential in the dimension of the input data to high dimensional data sets. Interestingly, it is very difficult to check that a given matrix has the Johnson-Lindenstrauss property even though a random matrix has the property with very high probability. I recall reading somewhere the description "finding hay in a haystack" for this problem.

Answer 4

I will interpret your question in this way: Are there any example of a theorem which proof uses a probability technique to prove the existence of some object where it is proven that the example exists but its explicit construction is impossible?

An example can be the theorem:

Every large even number can be expressed as the sum of a prime and the product of at most b primes.

Rényi proved this theorem using a generalisation of ''the large sieve'' method that can be seen as an application of a probabilist method:

Rényi, A. On the large sieve of Yu. V. Linnik. Compositio Mathematica, 8, 68-75 (1956).

Rényi, A. Un nouveau théorème concernant les fonctions indépendantes et ses applications à la théorie des nombres. J. Math, pures et appi. (9), 28, 137-149 (1949).

Rényi, A. Sur un théorème général de probabilité. Ann. Inst. Fourier, 1, 43-52 (1949).

Answer 5

There are many such results ( methods) to be found in functional analysis, more precisely, the theory of Banach spaces. A spectacular example is Gluskin's estimate from below for the diameter of the class of $n$-dimensional Banach spaces under the Banach-Mazur distance which involved a probabilistic proof of the existence of a pair of Banach spaces which are far apart in a suitable sense ( MR 0609798).

Answer 6

Regarding your second question, there is indeed a constructive proof showing that there are sparse graphs with arbitrarily high chromatic number due to Lovász (unfortunately behind a paywall). However, you can read this very lively survey by Nesetril on the history of the problem. Indeed, the question of explicit constructions was already raised by Erdos in the beginning. The survey starts with the many constructions for the triangle-free case and proceeds to the current state-of-the-art, passing through many interesting topics (including Kneser graphs and expanders) along the way.

Answer 7

Let the $V_n$ be iid random variables with $P(V_n=\pm 1)=1/2$. Almost surely, the discrete Schrodinger operator $$ (Hu)_n = u_{n+1} + u_{n-1} + V_n u_n $$ on $\ell^2(\mathbb Z)$ has dense pure point spectrum (aka Anderson localization). I don't think anyone can describe a concrete $\pm 1$ sequence for which this happens.

Answer 8

The best deterministic constructions of matrices with the restricted isometry property are much worse than random matrices. Matrices with the restricted isometry property are important in compressed sensing, and finding better deterministic matrices is a subject of active research.

Here the quality of the matrix is the number of columns for a matrix with the restricted isometry property and a fixed number of rows, which represents how much one can compress the data in a compressed sensing situation.

Answer 9

Somewhat surprisingly, Jean Bourgain's 1985 theorem about embedding finite metric spaces into Hilbert spaces was not mentioned yet. Since metrics have not mentioned at all in this thread, let me mention this example now.

The topic of representing prescribed, possibly strange finite metric spaces 'as best one can' by non-strange, traditional metric spaces is important e.g. in computational biology. Very briefly, I think the essence of all of this is

not to have to store a table of pairwise distances among any two of a large number of proteins, which after all would take space quadratic in the number of 'specimens', rather label/represent each protein by an element of a traditional metric space, and then calculate a distance the traditional way, from the traditional representatives, on an as-needed-basis.

For this to result in only a small error of approximation (of the 'true' distance w.r.t. some new-fangled 'similarity distance' between proteins), one needs to know how well such 'representations'/'low-distortion embeddings' can be done in principle.

Bourgain used the "probabilistic method" to prove a lower bound on how well this can be done.

The publication is Jean Bourgain: On lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics March 1985, Volume 52, Issue 1–2, pp 46–52, and the abstract reads:

"It is shown than any $n$ point metric space is up to $\log n$ lipeomorphic to a subset of Hilbert space. We also exhibit an example of an $n$-point metric space which cannot be embedded in Hilbert space with distortion less than $(\log n)/(\log\log n)$, showing that the positive result is essentially best possible. The methods used are of probabilistic nature. For instance, to construct our example, we make use of random graphs."

(emphasis added)

Answer 10

Thinking about my own question, I had another question that came to my mind. Take any real number and write its binary representation. With probability $1$ the proportion of zeroes and ones is the same and is equal to $1/2$. We can say that for its 3-representation and the representation in any system the proportion of numbers used is equal with probability $1$. So almost any number has this property.

But can we find any concrete number and prove this property for it?...