Content deleted Content added
m Move footnotes to the right place |
m custom spacing in math formulas (via WP:JWB) |
||
| (One intermediate revision by one other user 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 58:
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''<sup>1/''g''
:'''Property 1.''' {{mvar|G}} contains at most {{math|''n''/2}} cycles of length less than {{mvar|g}}.
| |||