[FOM] counting arguments?

Stephen G Simpson simpson at math.psu.edu
Fri Oct 24 18:49:00 EDT 2003

Describing the probabilistic method in finite combinatorics, David
Corfield 21 Oct 2003 writes:

 > 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"os. In a few cases the proof can be
 > translated to a counting argument, but this is not so in general.

This seems wrong, or at least imprecise.  Probabilistic arguments in
finite combinatorics always come down to counting.  Isn't that so?
Or, are you reserving the term "counting argument" for some special
type of (what mathematicians usually refer to as) counting arguments?

I assume you are referring to probabilistic existence proofs in
*finite* combinatorics, since that is where Erd"os and his colleagues
developed the method.  The probabilistic existence proof of expander
graphs is a particularly nice example.

Of course there are plenty of *infinitary* probabilistic existence
proofs which cannot be translated into counting arguments.

What is the alleged philosophical interest of all this?

Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University

More information about the FOM mailing list