[FOM] Erdos type probabilistic arguments

[David Corfield]

A while ago, John Baldwin wrote:

>Corfield wrote:
[in a post about Bayesianism]

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

I'm sure there are people on this list that know more than I do about this.
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.

After thinking about this for a moment you realise you could reformulate
the argument in terms of counting number of colourings. I believe however
that for other uses of such probabilistic methods it is not known how to
translate them similarly.

David Corfield