[FOM] Counting arguments

[Lengyel, Florian]

Urquhart:

I think it is rather trivially true that
any probabilistic argument in finite
combinatorics can be rewritten as 
a counting argument.  This is because
probability in finite spaces is simply
the ratio of two finite cardinalities.
...

However, from the heuristic point of view,
the language of probability theory is extremely
helpful.  Joel Spencer puts it rather well in 
his "Ten Lectures on the Probabilistic Method"
p. 2:

	When presented with the probabilistic method,
	the probabilist J. Doob remarked: "Well, this
	is very nice, but it's really just a counting
	argument."  With the advantage of hindsight I 
	respectfully disagree.  As we shall see, ...,
	notions of probability permeate the probabilistic
	method.  To reduce the arguments to counting,
	although it is technically feasible, would be 
	to remove the heart of the argument.

This matter of heuristic suggestiveness is very important
for mathematical practice, though I don't think we can
say much about it with current tools of mathematical logic.


Lengyel:

Alon, Erdos and Spencer write something stronger in "The Probabilistic
Method." They say that in practice, the use of probability theory in
probabilistic combinatorial arguments is essential, and that "it would be
hopeless to replace many of the tools appearing in this book, including, for
example, the second moment method, the Lovasz local lemma, and the
concentration via martingales by counting arguments, even when these are
applied to finite probability spaces." This goes beyond the assertion of
Bollobas that for for his purposes, probability is a convenient language.

Probabilistic combinatorics, in contrast to the probability theory of a
finite probability space, is often concerned with formulating and proving
certain limit statements involving parameterized families of events
belonging to an infinite sequence of finite probability spaces. On account
of its reliance on probabilistic and asymptotic methods, while it may be
true that any one probability space of such an infinite sequence of finite
probability spaces is finite, to sidestep the asymptotics of the infinite
sequence of spaces, and to leave unanalyzed the mathematical difficulties
that could arise in attempting to eliminate probability theory from the
picture--e.g., the proofs could become unmanageable--strikes me as an
oversimplification of the method.  

I offer an example from my own work, "Cellular telephone networks and random
maps in hypergraphs," with Janos Pach and Ariel Halpert, which uses the
martingale and large deviation techniques Spencer mentions, to illustrate
how considerations of asymptotics and limit processes can inform decisions
about what one decides to count; in this case, the goal was a limit
probability distribution (not just a zero-one law). Such considerations go
beyond counting the number of points of a finite set.

In that paper, I used a technique of Gosper, Wilf and Zeilberger to attempt
to find a hypergeometric normal form of the enumeration formula for a
certain class of functions, the almost injective functions.  It turns out
that the enumeration formula of the almost injective functions are not
machine summable; there is an indefinite summation formula, but this cannot
be reduced to a finite sum of dissimilar generalized hypergeometric
functions. Richard Stanley wrote down in email a nice rational generating
function for the number of such things; however, the binomial coefficient
enumeration formula it yields can easily be shown not to be machine
summable. Attempts to split that formula into machine summable
asymptotically significant parts didn't work. 

However, I found another enumeration method, based on a classification of
the almost injective functions by a regular language, which made possible
splitting the class of almost injective functions into two disjoint parts,
whose enumeration formulas had the following useful property for
probabilistic combinatorics. The enumeration formula of the first part was
machine summable and asymptotically significant (it yields a limit
probability distribution for the number of almost injective functions); the
enumeration formula of the second part was not machine summable, however, it
was asymptotically negligible. The first class of functions had an algebraic
property, perhaps related to their machine summability: they could be
represented (in a certain sense) by a regular language closed under
concatenation.

The hypergeometric normal form of the machine summable asymptotically
significant enumeration formula was of a type (type 3F2) for which it is
known there is no algebraic identity analogous to Gauss's gamma function
identity. However, that 3F2 formula is asymptotically equivalent to a 2F1
for which Gauss's identity holds, and it turns out one can use this
equivalence to derive a limit probability distribution for the number of
almost injective functions. Another result in that paper was a more or less
direct application of martingale techniques in Spencer's book.

Probabilistic combinatorics is concerned with the asymptotics of infinite
sequences of finite probability spaces; accordingly, considerations of limit
processes and asymptotics of infinite sequences of finite probability
spaces--considerations which do not arise if one only considers a finite
probability space in isolation--can inform one's choice of what to count. 

-FL