[FOM] Re: counting arguments?

[Timothy Y. Chow]

Stephen G Simpson <simpson at math.psu.edu> wrote:
> When you say "probabilistic combinatorics", what exactly are you
> referring to?  Perhaps you mean topological/ergodic Ramsey theory, as
> pioneered by H. Furstenberg.  This is quite different from probabilistic
> existence proofs in finite combinatorics, as pioneered by Erd"os.  When
> I said that it all boils down to counting, I was referring to the Erd"os
> stuff, not the Furstenberg stuff.

O.K., it's good to try to be precise here.  I understand the distinction
you're making here, but I wonder if it's as sharp as you make it sound.
I don't really keep up with all the latest developments in probabilistic
combinatorics beyond scanning some abstracts and listening to some talks,
but my impression is that even the "Erdos-style" existence proofs are
getting more sophisticated in the sense of invoking theorems from
probability that are, on the surface at least, stated and proved in
infinitary terms.  Theorems about concentration of measure (as promoted
by Milman, Talagrand, and others) come to mind as one example.

> Some specific questions and references are given in a recent survey
> paper by me and Friedman on open problems in reverse mathematics.

Very interesting.  Where can I find this survey paper?

It occurs to me now that there is another distinction here, between two
different sense of "reduction to counting."  There is the reverse-
mathematical sense, where "reduction to counting" means something like
demonstrating provability in PA or an even weaker system.  From your
message I take it that you agree, modulo fine distinctions in the
definition of the term "probabilistic arguments in finite combinatorics,"
that it is not clear that everything reduces to counting.

But there is another sense, which might be closer to what David Corfield
and the practitioners of the field mean.  Namely, a probabilistic argument
"does not reduce to counting" if the way people psychologically
conceptualize the proof seems to use probability in an essential way.
Certainly if the proof does not reduce to counting in the reverse-
mathematical sense, then it doesn't reduce to counting in the second
sense, but the converse need not hold.  That is, maybe the use of
probability is eliminable, but it's not clear how that could be done.
Or even stronger, maybe it's known in principle how to eliminate the
probability, but psychologically it is far easier to discover and
understand the proof if it is cast in probabilistic terms.

Similar psychological phenomena are commonplace elsewhere in math,
e.g., sometimes it's easier to find a proof using nonstandard analysis
even if a posteriori we can use a transfer principle to eliminate it.

What I think Corfield may be suggesting is that it is a philosophically
interesting question to make precise this latter sense, and to say
something more illuminating than "it's just human psychology."  I am
not sure how one would go about making this latter notion of reduction
precise enough to prove theorems about it, but I can imagine it being
done.  Concepts from classical f.o.m. would of course be relevant but
I think new ideas would also be needed.

Tim