Probabilistic method: Difference between revisions

Revision as of 02:05, 5 January 2024

Latest revision as of 01:18, 19 May 2025

(9 intermediate revisions by 9 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 54:

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.

----

{{notelist}}

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

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

Line 94 ⟶ 90:

*[[Interactive proof system]]

*[[Las Vegas algorithm]]

*[[Incompressibility method]]

*[[Method of conditional probabilities]]

*[[Probabilistic proofs of non-probabilistic theorems]]

Line 100 ⟶ 97:

== Additional resources ==

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

==References==

Line 110 ⟶ 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. 296; {{ISBN|0 444 81624 0}}

{{Reflist}}

==Footnotes==

{{Reflist}}

{{notelist}}

{{Authority control}}

Line 118 ⟶ 117:

[[Category:Combinatorics]]

[[Category:Mathematical proofs]]

[[Category:Probabilistic arguments|method]]