# [FOM] Erdos type probabilistic arguments

David Corfield david.corfield at philosophy.oxford.ac.uk
Mon Oct 27 11:01:17 EST 2003

```A while ago, John Baldwin wrote:

>Corfield wrote:

>>  one thought
>>I had along these lines concerns probabilistic existence proofs of the
>>Erdos variety.
>
>>The existence of a mathematical object is established by proving that the
>>probability of its existence is positive. The technique was first devised
>>by Paul Erdös. In a few cases the proof can be translated to a counting
>>argument, but this is not so in general.

>Can you elaborate on the last sentence.  What does it mean to say `this is
>not a counting argument'.

It's easy enough to understand the translation of some probabilistic proofs
into
counting arguments. E.g., a common way to prove the lower bound for
the Ramsey numbers R(k,k) is to take the complete graph on n nodes,
colour the edges at random independently with 2 colours, then find the
expected
number of monochromatic complete subgraphs on k nodes. If n is chosen
small enough, then the expectation is less than 1, so it must be possible to
have all complete subgraphs on k nodes non-monochromatic.