Probabilistic method: Difference between revisions

Revision as of 22:59, 8 November 2024

Latest revision as of 01:18, 19 May 2025

(6 intermediate revisions by 6 users not shown)

Line 6:

==Introduction==

If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Thus, by [[contraposition]], if the probability that a random object chosen from the collection has that property is nonzero, then some object in the collection must possess the property.

Similarly, showing that the probability is (strictly) less than 1 can be used to prove the existence of an object that does ''not'' satisfy the prescribed properties.

Line 55:

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.

===Second example===

----

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''−1}}. We show that with positive probability, {{mvar|G}} satisfies the following two properties:

{{notelist}}

:'''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}}. The 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>

and each of them is present in {{mvar|G}} with probability {{math|''pⁱ''}}. Hence by [[Markov's inequality]] we have

:<math>\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} = gn^{-\frac{1}{g}} = o(1).</math>

: Thus for sufficiently large {{mvar|n}}, property 1 holds with a probability of more than {{math|1/2}}.

:'''Property 2.''' {{mvar|G}} contains no [[Independent set (graph theory)|independent set]] of size <math>\lceil \tfrac{n}{2k} \rceil</math>.

'''Proof.''' Let {{mvar|Y}} be the size of the largest independent set in {{mvar|G}}. Clearly, we have

:<math>\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1),</math>

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).

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 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==

Line 72 ⟶ 97:

== Additional resources ==

* [https://ocw.mit.edu/courses/18-226-probabilistic-methodmethods-in-combinatorics-fall-20202022/ Probabilistic Methods in Combinatorics], MIT OpenCourseWare

==References==

Line 82 ⟶ 107:

* Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, {{ISBN|978-981-3149-84-7}}, 2017

* Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp.&nbsp;296; {{ISBN|0 444 81624 0}}

{{Reflist}}

==Footnotes==

{{Reflist}}

{{notelist}}

{{Authority control}}