Opinion 58: `I Saw Their Proof Now I'm a Believer':
The MarcusTardos Proof of the FürediHajnal
and StanleyWilf Conjectures
By Doron Zeilberger
Written: Dec. 3, 2003
Once I thought that proofs of longstanding conjectures had to
be difficult. After all didn't brilliant people make them,
and didn't these people, and many other brilliant people,
unsuccessfully try to prove them?
Isn't that a metaproof that the proof, if it exists, should be
long, difficult, and ugly? And if not, shouldn't they, at least,
contain entirely new ideas and/or techniques?
Then I saw the
proof
by
Adam Marcus
and
Gabor Tardos
of the
Füredi
Hajnal
conjecture, that was known, thanks to
Martin Klazar,
to imply the
Stanley

Wilf
conjecture. Brilliant people like
Noga Alon
and
Ehud Friedgut
came very very
close,
and the great enumerator
Miklos Bona proved it
for an
important class
of permutations. Not to forget yours truly who was sure that
one day it would be shown to follow from his pet concept,
Enumeration Scheme.
I am sure that many other, equally brilliant people, also tried
to attack it.
When you read the beautiful onepage proof, you realize that
"all" that Marcus and Tardos used were two of the most basic
tools of our trade, the
pigeonhole principle, and
divideandconquer, or equivalently, a takeoff of
the fact that the sequence a(n):=2^{n}, not only satisfies
the linear ("defining") recurrence, a(n)=2*a(n1), but lots
of nonlinear recurrences as well: a(n)=a(n/k)^{k},
for any k, and we are free to use the k that suits us.
This basic idea is also behind
the Fast Fourier Transform and the Renormalization
Group method in physics.
But this by no means detracts from their achievement! Quite
the contrary.
If they would have used heavy guns and/or brandnew methods
or thousands of hours of computer time, we would all have had an excuse
why we didn't find it ourselves. Their "proof from the
book" is so beautiful and compelling in its simplicity, that
we are forced to kick ourselves for not coming up with it ourselves.
But let's stop whining and start rejoicing. OK, we didn't score
on this one, but there are many fish in the sea.
It is very unlikely that the FürediHajnal and
StanleyWilf conjectures are the only open problems that
have nice short proofs using existing methods.
[Of course, dear old uncle Paul (Erdös), believed that
all problems have such "proofs from the book", but he was
an incurable optimist].
We have to resist the natural tendency
not to try simple things, assuming that `someone would
surely have thought about it before, so why bother?'.
It is worth trying, because you never know, and besides, it is fun
to try, even if you fail.
Perhaps even RH and P vs. NP have such simple proofs?
Probably not!
The same thing is true for any specific open problem.
But the precedent of the MarcusTardos proof
(and the AgrawalKayalSaxena primality algorithm, and
even de Branges's proof of Bieberbach and Apéry's zeta(3),
and there are quite a few other examples),
show that, with probability 1epsilon, there exist
quite a few fairly famous open problem
that are amenable to simple (but of course, ingenious) arguments
in the style of MarcusTardos. The metaproblem is: which ones?
So let's get to work, and
Keep
It
Simple
Stupid!
P.S.: I loved the MarcusTardos proof so much that I wrote
a
Loving Rendition. Enjoy!
Doron Zeilberger's Opinion's Table of Content
Doron Zeilberger's Homepage