Probabilistic method: Difference between revisions

Revision as of 08:44, 4 January 2023

Revision as of 22:33, 17 January 2023

Line 1:

{{short description|Nonconstructive method for mathematical proofs}}

TheIn [[mathematics]], the '''probabilistic method''' is a [[nonconstructive proof|nonconstructive]] method, primarily used in [[combinatorics]] and pioneered by [[Paul Erdős]], for [[mathematical proof|proving]] the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the [[probability]] that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for ''certain'', without any possible error.

This method has now been applied to other areas of [[mathematics]] such as [[number theory]], [[linear algebra]], and [[real analysis]], as well as in [[computer science]] (e.g. [[randomized rounding]]), and [[information theory]].

Line 17:

==Two examples due to Erdős==

Although others before him proved theorems[[theorem]]s via the probabilistic method (for example, Szele's 1943 result that there exist [[tournament (graph theory)|tournaments]] containing a large number of [[Hamiltonian cycle]]s), many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the [[Ramsey's theorem|Ramsey number]] {{math|''R''(''r'', ''r'')}}.

===First example===

Suppose we have a [[complete graph]] on {{mvar|n}} [[vertex (graph theory)|vertices]]. We wish to show (for small enough values of {{mvar|n}}) that it is possible to color the [[edge (graph theory)|edges]] of the [[graph (discrete mathematics)|graph]] in two colors (say red and blue) so that there is no complete [[subgraph (graph theory)|subgraph]] on {{mvar|r}} vertices which is monochromatic (every edge colored the same color).

To do so, we color the graph randomly. Color each edge independently with probability {{math|1/2}} of being red and {{math|1/2}} of being blue. We calculate the expected number of monochromatic subgraphs on {{mvar|r}} vertices as follows:

For any set <math>S_r</math> of <math>r</math> vertices from our graph, define the variable <math>X(S_r)</math> to be {{math|1}} if every edge amongst the <math>r</math> vertices is the same color, and {{math|0}} otherwise. Note that the number of monochromatic <math>r</math>-subgraphs is the sum of <math>X(S_r)</math> over all possible subsets[[subset]]s <math>S_r</math>. For any individual set <math>S_r^i</math>, the [[expected value]] of <math>X(S_r^i)</math> is simply the probability that all of the <math>C(r, 2)</math> edges in <math>S_r^i</math> are the same color:

:<math>E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}</math>

Line 38:

:<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}}.</math>

Consider what happens if this value is less than {{math|1}}. Since the expected number of monochromatic {{mvar|r}}-subgraphs is strictly less than {{math|1}}, there exists a coloring satisfying the condition that the number of monochromatic {{mvar|r}}-subgraphs is strictly less than {{math|1}}. The number of monochromatic {{mvar|r}}-subgraphs in this random coloring is a non-negative [[integer]], hence it must be {{math|0}} ({{math|0}} is the only non-negative integer less than {{math|1}}). It follows that if

:<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1</math>

(which holds, for example, for {{mvarmath|''n'' {{=}}= 5}} and {{mvarmath|''r'' {{=}}= 4}}), there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. {{efn|

The same fact can be proved without probability, using a simple counting argument:

* The total number of ''r''-subgraphs is <math>{n \choose r}</math>.

Line 51:

}}

By definition of the [[Ramsey number]], this implies that {{math|''R''(''r'', ''r'')}} must be bigger than {{mvar|n}}. In particular, {{math|''R''(''r'', ''r'')}} must [[exponential growth|grow at least [[exponential growth|exponentially]] with {{mvar|r}}.

A weakness of this argument is that it is entirely [[nonconstructive proof|nonconstructive]]. Even though it proves (for example) that almost every coloring of the complete graph on {{math|(1.1)^''r''}} vertices contains no monochromatic {{mvar|r}}-subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been [[open problem|open]] for more than 50 years.

----

Line 62:

A 1959 paper of Erdős (see reference cited below) addressed the following problem in [[graph theory]]: given positive integers {{mvar|g}} and {{mvar|k}}, does there exist a graph {{mvar|G}} containing only [[cycle (graph theory)|cycles]] of length at least {{mvar|g}}, such that the [[chromatic number]] of {{mvar|G}} is at least {{mvar|k}}?

It can be shown that such a graph exists for any {{mvar|g}} and {{mvar|k}}, and the proof is reasonably simple. Let {{mvar|n}} be very large and consider a random graph {{mvar|G}} on {{mvar|n}} vertices, where every edge in {{mvar|G}} exists with probability {{math|''p'' {{=}} ''n''^{1/''g''&hairsp;−1}}}. We show that with positive probability, {{mvar|G}} satisfies the following two properties:

:'''Property 1.''' {{mvar|G}} contains at most {{math|''n''/2}} cycles of length less than {{mvar|g}}.

'''Proof.''' Let {{mvar|X}} be the number cycles of length less than {{mvar|g}}. NumberThe number of cycles of length {{mvar|i}} in the complete graph on {{mvar|n}} vertices is

:<math>\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}</math>

Line 82:

when

:<math>y = \left \lceil \frac{n}{2k} \right \rceil\!.</math> Thus, for sufficiently large {{mvar|n}}, property 2 holds with a probability of more than {{math|1/2}}.

For sufficiently large {{mvar|n}}, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).

Line 88:

Here comes the trick: since {{mvar|G}} has these two properties, we can remove at most {{math|''n''/2}} vertices from {{mvar|G}} to obtain a new graph {{math|''G′''}} on <math>n'\geq n/2</math> vertices that contains only cycles of length at least {{mvar|g}}. We can see that this new graph has no independent set of size <math>\left \lceil \frac{n'}{k}\right\rceil</math>. {{math|''G′''}} can only be partitioned into at least {{mvar|k}} independent sets, and, hence, has chromatic number at least {{mvar|k}}.

This result gives a hint as to why the computation of the [[Graph coloring|chromatic number]] of a graph is so difficult: even when there are no local reasons (such as small cycles) for a graph to require many colors the chromatic number can still be arbitrarily large.

==See also==