%narra.tex: How Adam Marcus and Gabor Tardos Divided and Conquered ...
%%a Plain TeX file by Doron Zeilberger (xx pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
How Adam Marcus and Gabor Tardos Divided and Conquered 
}
\centerline
{
the Stanley-Wilf Conjecture
}
\centerline
{
(An \'Etude in Paramathematics)
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
First version: Oct. 15, 2004.
Transcript of a Colloq. talk given at Georgia Tech, Oct.
1, 2004, 4:05-4:55pm.
Supported in part by the NSF.
} 
}

\quad\quad\quad\quad\quad
{\it Dedicated to Apostolos Doxiadis, the First (and Foremost!) 
Paramathematician}

...Thanks Tom[Morely] for this lovely introduction. Now I have to
reciprocate and tell you that when I met Tom's thesis advisor, Dick
Duffin, for the first time, in 1976, he told me, very excitedly,
about his ``{\it brilliant student Tom Morely, who is the best
student he has ever had}''. At the time I was only mildly impressed,
OK, he is best amongst a random group of five or ten mathematicians.
Only later did I find out that the set of Duffin students
contains Raul Bott and Hans Weinberger...


Good afternoon! Thank you all for coming. You are really lucky, since
I don't accept all invitations to speak. For most people,
the {\bf number of distinct talks} is less than the
{\bf number of talks}.
It follows, by the {\bf pigeon-hole principle}
(that will show up again and again during this talk), 
that people don't mind
{\bf repeating themselves}. Myself, I never repeat a talk, and hence
can only afford to accept so many invitations.

I came here for two
reasons. First, I couldn't say no to my good friend and collaborator,
Stavros Garoufalidis, and second, it gives me an opportunity to
talk about a wonderful recent result in combinatorics, co-authored
by one of you!, who, besides. is a {\it mere} (mathematical) epsilon,
a first-year grad student. You are really lucky to have amongst
you Adam Marcus, the co-prover, with Gabor Tardos, of the
celebrated F\"uredi-Hajnal and Stanley-Wilf conjectures.
When I suggested the title, my old friend Dick Duke wrote me
E-mail that Adam already spoke about this in the combinatorics
seminar a few weeks earlier. I replied that such a beautiful
result can and should be repeated as often as possible.

Besides, I also had another reason for speaking about this.
I wanted to give an {\it example} of an {\bf interesting} mathematical
talk. Most math talks are extremely boring, since most mathematicians
have no clue on how to
present their (or other people's) results in an interesting way.
Of course, {\it doing} mathematics is very exciting, but somehow
mathematicians, when they write it up, or lecture about it,
squeeze most of the excitement out. Also they use way toooo
much notation, definitions, formulas, etc. etc. and one gets
an overflow of information. What they hardly ever deliver is
a {\bf good story}.

How many people have read {\it Uncle Petros and the Goldbach Conjecture}
by Apostolos Doxiadis? [more than half of the about forty-five people
raise their hands]. Now, this same Doxiadis preaches that 
we should use {\bf stories} when we teach math to our students.
He even coined a new name for such an activity:
{\bf paramathematics}, and {\bf paramathematicians}
for its practitioners. He needed to create a new 
{\bf para-profession}, since he
does not believe that professional mathematicians can meet this
challenge. I should also mention my former colleague
John Allen Paulos, who wrote a lovely book `{\it Once Upon a Number}'
linking math to stories.

In this talk, I want to {\it prove by example} that it is
possible to present {\it cutting-edge} research in the form of
a {\it good story}. I admit that not all of mathematics is so easily
transferable to the story-medium, but combinatorics is!
Alas, many combinatorialists
have a complex about their field, that for a long time was
scorned by the main-stream mafia, {\it because} the problems
can be understood by everyone. 
(Of course, solving the problems is another story.
As we all know, easily-stated
problems are the hardest to prove! Witness the Goldbach Conjecture.)
Because of that complex, many combinatorialists are more 
Catholic than the Pope and more Bourbakists than Dieudonn\'e,
and present their results in the formal, boring, style of
the ruling mandarins. But, now that combinatorics is socially
respectable, it is time to free ourselves from these hangups
and present our beautiful combinatorial results in the
most attractive form, that is through {\it stories}. 


Let me first tell you about the {\bf significance} of the Stanley-Wilf 
conjecture.
I am sure that you all know that Richard Stanley is the {\bf numero uno} 
guru in enumerative and
algebraic combinatorics, and Herb Wilf is definitely amongst the 
{\bf top five}.
Yet neither Stanley, nor Wilf, nor any of the many skilled enumerators 
that tried
very hard to prove it (yours truly included!), succeeded. What made it 
even more
amazing and frustrating was the fact that the Marcus-Tardos proof may be
presented in {\bf half a page}.
[Here I distributed a half-page handout, a copy of my short
article from my Personal Journal].
Of course, it is {\bf gorgeous}!

What is the Stanley-Wilf conjecture?
Suppose that you have $n$ people, all of different heights, and you want
to arrange them in a line, in how many ways can you do this?
$n!$ of course, where $n!$ is short for one times two times three 
$\dots$ times $n$.
Now suppose that you want to avoid the `pattern' $abc$, i.e. you forbid that
there exist three people, anywhere, such that the tallest will be ahead of
the second-tallest, and the second-tallest ahead of the shortest.
For example, calling the $5$ people $1,2,3,4$ and $5$,
$32154$ avoids $abc$ but $15324$ does not. It is well-known that the
number of $abc$-avoiding permutations of length $n$ is the Catalan number 
which is
two $n$ choose $n$ divided by $n+1$ which is roughly $4$ to the power $n$,
and hence of {\bf exponential} growth, which is qualitatively less
than the rate of growth of $n$ factorial, that, thanks to Stirling, is
{\bf super-exponential}. Now the Stanley-Wilf conjecture asserts
that this {\bf exponential growth} is true for any {\bf pattern},
of {\it arbitrary} length. Initially
it was only known for few special
cases, and later, thanks to Miklos Bona, for a rather large infinite 
family, but
the full conjecture was wide open.

Adam Marcus and Gabor Tardos did not prove this conjecture directly, but 
via another
conjecture, due to Zolt\'an F\"uredi and P\'eter Hajnal, that was previously
known, thanks to Martin Klazar, to imply the Stanley-Wilf conjecture.
If I only talked about their proof, I'd be done in twenty minutes.
So let me first tell you, in {\bf story-format},  the
classical proofs of the celebrated Ramsey and van der Waerden theorems.
Both of these warm-ups contain the same central ideas as the Marcus-Tardos
proof, namely {\bf pigeon-hole} and {\bf modularity} (or `divide-and-conquer'),
and every combinatorialist is familiar with these proofs, and hence with
these ideas. This makes it all the more frustrating that we all missed this gem.


{\bf Ramsey}

Suppose that you want to make a party, where everyone has strong feelings, every
pair of two people either love each other or hate each other. Note that there is
no unrequited love. We want to avoid {\it both} {\bf love-triangles} and {\bf hate-triangles} 
(i.e. three people who mutually love [hate] each other).
In a party of five, it is possible if

{\it Abe loves Bob, Bob loves Charles, Charles loves Doron, Doron loves Ed, and Ed loves Abe, }

while

{\it Abe hates Charles, Charles hates Ed, Ed hates Bob, Bob hates Doron and Doron hates Abe .}

But if the party-size is six, then 
Frank Plumpton Ramsey tells us that {\bf triangles} are
 {\bf unavoidable}. 
This fact is denoted by 
$$
R(3,3)=6 \quad.
$$
I will prove to you something {\it weaker}:
$$
R(3,3) \leq 16 \quad,
$$
by describing an {\bf algorithm} for finding a love-triangle or hate-triangle
in any party of $16$ people.

Call a  person at a party a {\bf lover} if he has at least as many  friends as enemies,
amongst the guests of the party, otherwise call him a {\bf hater}.

Look at the shortest person, let's call him Abe.
If Abe is a lover, kick out of the party all his enemies, otherwise, kick out all his lovers.
Now Abe has {\bf consistent} feelings towards all the remaining (at least) eight guests.
Let Abe remain in the room, but don't consider him any longer part of the party. 

Look at the shortest person amongst the remaining eight guests, let's call him Bob.
If Bob is a lover, kick out of the party all his enemies, otherwise, kick out all his lovers.
Now Bob has {\bf consistent} feelings towards all the remaining (at least) four guests.
Let Bob remain in the room, but don't consider him any longer part of the party. 

Look at the shortest person amongst the remaining four guests, let's call him Charles.
If Charles is a lover, kick out of the party all his enemies, otherwise, kick out all his lovers.
Now Charles has {\bf consistent} feelings towards all the remaining (at least) two guests.
Let Charles remain in the room, but don't consider him any longer part of the party. 
Call the two remaining guests Doron and Ed. (If it so happens that 
more than two guests survived, pick any two at random to be Doron and Ed.)
If Doron and Ed love each other they are both lovers, otherwise they are
both haters.

At the end of the day, there are {\bf five} surviving people  in the room:
Abe, Bob, Charles, Doron, and Ed,
each of them with {\bf consistent} feelings towards those that come latter in the list.
By the  {\bf pigeon-hole principle}, either there are {\bf at least three } lovers,
or {\bf at least three} haters.
In the former case they form a {\bf love triangle}, and in the
latter case, a {\bf hate triangle}. {\bf Quod Erat Demonstatum}.

This argument can be easily extended to show that
any party with $2^{2n-2}$ guests must contain either
an $n$-clique or an $n$-anti-clique.
Hence
$$
R(n,n) \leq 2^{2n-2} \quad,
$$
which is not as good as the {\it best known} upper bound, but is pretty-damn-close,
since it gives the same {\it asymptotics}, which  is $O(4^n)$.
It would be major breakthrough to replace the $4$ by
$3.99999999999$.

{\bf van der Waerden}

In this part of the talk, I will use {\bf stories} literally, by talking about
stories and their constituent elements: {\it letters}, {\it words},
{\it sentences}, {\it paragraphs}, etc.


The classical van der Waerden theorem is usually phrased in terms of {\bf colorings}
of integers. But a more up-do-date, and {\it apt}, formulation is via
{\bf ESL}, which are short for Equally Spaced Letters.

You must have heard, a few years ago, the big controversy about the {\bf Bible Codes}
that was espoused in Michael Drosnin's best-seller, and `discovered' by
Jerusalem mathematician Eliyahu Rips, and his two cronies.
They claimed to have found amazing predictions in the Bible, by finding 
relevant words or names in the Torah (written one-dimensionally without any spaces)
in {\bf Equally-Spaced} places, for example
at the 3003-th 4002-th, 5001-th places.
The van der Waerden theorem tells you, essentially, 
that if the text is long enough, some `meaningful'
ESLs (of any length!)  are {\bf inevitable}.

Fix your alphabet, and let it have $k$ letters;
$k$ could be $2$ (the $0$-$1$ alphabet of cyberworld), 
$4$ (the ACTG alphabet of life),
$22$ (the aleph-tav 
Hebrew alphabet), $24$ (the $\alpha-\omega$ Greek alphabet),
$26$ (the A-Z English alphabet), etc., it does not matter. Also let $L$ be another positive integer.
The van der Waerden theorem
tells you that there exists a {\bf word-length} such that
{\bf every word} of that length is {\bf guaranteed} to have {\bf at least one ESL}
of length $L$ of the form $aaa \dots a$, ($a$ repeated $L$ times) for
{\bf some} letter of the alphabet $a$. In the case of English, and $L=5$
you can find a word-length $N$ such that each and {\it every}  one of the
$26^N$ words of length $N$, is guaranteed to have an ESL of the
form AAAAA, or BBBBB, or CCCCC, or
$\dots$, or ZZZZZ. In other words,
for every conceivable word of that length, you can find 
$L$ {\bf equally-spaced} locations that contain the {\bf same} letter.
From now on we will take an $L$-ESL to mean 
an {\bf arithmetical progression} of locations that contain the {\bf same letter}.
For example {\bf adoronod} contains a $3$-ESL (the letter {\bf o} at locations
3,5,7).

Reading a story (or any text for that matter) can be 
done on several levels.
Beginning readers combine {\bf letters} and read each letter separately.
Then we get better, and learn to recognize {\bf words}, and don't think
of the word {\it word} as `double-u oh ar dee ' but as a single {\bf module}.
Latter on we can recognize and {\bf encapsulate} phrases like
{\it thank you very much}, {\it if you know what I mean}, and {\it s'il vous plait}.
Some people can perhaps even perceive whole sentences at a glance, and if we were more talented
we could have gone for ever. 

The problem with natural language is that words have different lengths, that's why we
need an extra character, the {\it space} in order to delimit the individual words.
Also some 
sentences are longer than others, that's why we need a {\it period}. Some paragraphs
are longer than others, that's why we need to start them in a new 
(indented) {\it line}, some
chapters are longer than others, hence we need to use a {\it chapter-heading}, and so on.

Let's imagine an ideal (and artificial) language, where
all text is one-dimensional,
all words have the {\bf same} length,
and  every conceivable string of that length is a legitimate
word in the dictionary. Also decree that
all sentences have the {\bf same}  number of words,
all paragraphs have the {\bf same} number of sentences etc.
If that is the case, we no longer need 
delimiters like  space, period, line-break, etc.
We only need to know the word-length, sentence-length,
paragraph-length etc.

Now consider a super-duper long {\it text} 
written in our  alphabet.
Of course, we can read it {\bf letter-by-letter}.
But we can also read it {\bf word-by-word}, thinking of what used to be the 
`vocabulary'
as the new alphabet.  Continuing, we can also read it  {\bf sentence-by-sentence},
{\bf paragraph-by-paragraph},   or even {\bf chapter-by-chapter}, 
with increasingly gigantic `alphabets',
in  such meta-readings.

Suppose I {\bf know} how to find, for {\it any}  alphabet-size $K$,
an appropriate $(L-1)$-ESL-guaranteeing word-length.
I will now tell you how to use
this previous {\bf knowledge} to define
a (much larger!) $L$-ESL-guaranteeing word-length 
for the $k$-letter original alphabet.

For the sake of definiteness let's take
$k=4$ and think of the modules as letters, words, sentences, and paragraphs.

Decree that the length of 
every {\it word} in our new language (but still with
the same alphabet of size $k$) should be {\bf twice} the above 
$(L-1)$-ESL-guaranteeing length.
Then it is true that even the {\it first half} of every word
has an $(L-1)$-ESL.

Now look at the vocabulary of all possible words. We {\bf know} that there
is a sentence-size such that every sentence must have an
$(L-1)$-ESL of {\bf words}. Decree that the length of 
every sentence should be
{\bf twice} that length, so that the {\it first half} of every sentence must have
an $(L-1)$-ESL of {\it words}.

Now look at the `sentence-book' of all possible sentences. We know that there
is a paragraph-size such that every paragraph must have an
$(L-1)$-ESL of {\bf sentences}. Decree that the length of every paragraph should be
{\bf twice} that length, so that the {\it first half} of every paragraph must have
an $(L-1)$-ESL of {\it sentences}.

Finally look at the `paragraph-book' of all possible paragraphs. We know that there
is a chapter-size such that every chapter must have an
$(L-1)$-ESL of {\bf paragraphs}. Decree that the length of 
every chapter should be
{\bf twice} that length, so that the {\it first half} of every chapter must have
an $(L-1)$-ESL of {\it paragraphs}.

So let's consider such a gigantic {\bf chapter}. I claim, that viewed
as a {\it word}, in the original alphabet, it must have an $L$-ESL.

First consider this chapter as
a {\it sequence of paragraphs}.
We know that its {\it first half}
contains an $(L-1)$-ESL of {\bf identical paragraphs}, let's call
these very special paragraphs (that are all {\bf identical} to each other, and
{\bf equally spaced})
$$
P_1 \quad , \quad P_2 \quad , \quad  \dots \quad ,\quad  P_{L-1} \quad .
$$
Since this takes place in the first half, it can
be continued to a would-be $L$-ESL
$$
P_1 \quad , \quad P_2 \quad , \quad  \dots \quad , \quad P_{L-1} \quad , \quad P_L  \quad ,
$$
but we know {\bf nothing whatsoever} about $P_L$.

Now take $P_1$ (which is the same as $P_2$, and the same as $P_3$ , ...
and the same as $P_{L-1}$) and {\bf read} it as a sequence of
{\bf sentences}. We know that the 
{\bf first half} of $P_1$ (and of course its buddies up to $P_{L-1}$)
has an $(L-1)$-ESL of {\bf sentences}, let's call them 
$$
P_{1,1} \quad , \quad P_{1,2} \quad ,  \dots \quad , \quad P_{1,L-1} \quad,
$$
and of course  we have it all mirrored in
$$
P_{2,1} \quad , \quad P_{2,2} \quad , \quad \dots \quad , \quad P_{2,L-1} \quad,
$$
$$
\quad\quad \dots \dots \dots 
$$
all the way up to
$$
P_{L-1,1} \quad , \quad P_{L-1,2} \quad , \quad \dots \quad , \quad  P_{L-1,L-1} \quad .
$$
Once again we extend it to a would-be ELS of size $L$
$$
P_{1,1} \quad , \quad P_{1,2} \quad , \quad \dots \quad , \quad P_{1,L-1} \quad , \quad P_{1,L} \quad,
$$
{\it except} that we know {\bf nothing} about 
$P_{1,L}$, and $P_{2,L}$ , $\dots$ , $P_{L-1,L}$.
But we do {\bf know} that these `random'  sentences
$$
\{ P_{1,L} \, , \, P_{2,L}\, , \, \dots \, ,  \, P_{L-1,L} \}
$$
are all {\bf equal to each other},
since they are at {\bf identical} places within their respective ({\bf identical}) paragraphs.

Now read $P_{1,1}$ (which is an identical twin of $P_{i,j}$ for all $i,j$ between $1$ and $L-1$),
as a sequence of {\bf words}. Once again we can find an $(L-1)$-ESL of {\bf words}
$$
P_{1,1,1} \quad , \quad P_{1,1,2} \quad , \quad \dots \quad , \quad P_{1,1,L-1} \quad,
$$
that is completely identical to
$$
P_{i,j,1} \quad , \quad P_{i,j,2} \quad , \quad \dots \quad , \quad P_{i,j,L-1} \quad,
$$
for all $i,j$ between $1$ and $L-1$, and extend it to a would-be-$L$-ESL
$$
P_{1,1,1} \quad , \quad P_{1,1,2} \quad , \quad \dots \quad , \quad P_{1,1,L-1} \quad, \quad
P_{1,1,L} \quad .
$$
Finally, we read the word $P_{1,1,1}$ (that is completely identical with
$P_{i,j,k}$, for $i,j,k$ between $1$ and $L-1$) as a sequence of {\bf letters}.
We know that the {\it first half} has an $(L-1)$-ESL  of (individual,
genuine!) {\bf letters} (in the original alphabet), let's call them
$$
P_{1,1,1,1} \quad , \quad P_{1,1,1,2}  \quad , \quad \dots \quad , \quad P_{1,1,1,L-1} \quad,
$$
that once again can be extended to
$$
P_{1,1,1,1} \quad , \quad P_{1,1,1,2} \quad , \quad \dots \quad , \quad P_{1,1,1,L-1} \quad, \quad
P_{1,1,1,L} \quad .
$$
where we know nothing about the {\bf letter} $P_{1,1,1,L}$
(but we do know that it is the same as $P_{i,j,k,L}$ for all $i,j,k$ between $1$ and $L-1$).

Now consider the {\bf five letters}
$$
P_{1,1,1,1} \quad , \quad P_{1,1,1,L} \quad , \quad P_{1,1,L,L}
\quad , \quad  P_{1,L,L,L} \quad ,  \quad P_{L,L,L,L} \quad .
$$
These are now individual letters (literally!) in the original four-letter alphabet.
By the {\bf pigeon-hole principle} (at least) two of these  are the same.
Say that the first and the last are identical
i.e. $P_{1,1,1,1}=P_{L,L,L,L}$, then
$$
P_{1,1,1,1} \quad , \quad P_{2,2,2,2} \quad , \quad \dots \quad , \quad P_{L,L,L,L} \quad ,
$$
is an $L$-ESL of {\bf letters}. Obviously they are equally-spaced and the
first $L-1$ of them are identical by construction, and the last one is
the same as the first (by assumption), hence by {\bf transitivity of equality},
they are all {\bf equal to each other}.

If the second and the fourth are the same, then
$$
P_{1,1,1,L} \quad , \quad P_{1,2,2,L} \quad , \quad \dots
\quad ,  \quad  P_{1,L,L,L} \quad,
$$
is an $L$-ESL. Again the first $L-1$ of them are identical to {\bf each other}
because they are situated at identical places in
identical words, and the last is identical to the first (by assumption).
We can do this for each of the five choose two possibilities
(in general $k+1$ choose $2$). Of-course the same argument works for
any size-alphabet, just continue to  books, super-books, $\dots$
up to level-$k$ super-letters.

The $L$-ESL-guaranteeing word-length (that turned out to be the
number of letters in a chapter),
even for a $2$-letter alphabet,
constructed by this argument (that I adapted from
Khinchin's lovely little gem of a book, where he attributes it to 
a lady mathematician called M. A. Lukomskaya) is {\bf eeeenormous}
(as Graham/Rothschild/Spencer would put it). It was considerably brought down in 1987
by Saharon Shelah, and reduced even further, by Fields-medalist Tim Gowers, to the pitiful:

{\bf two to the power two to the power two to the power two to the power two to the power} $L$

which is still (probably) far from the truth, that may be a 
{\bf constant times two to the power L}.

{\bf Feature Presenetation: the Marcus-Tardos Proof of F\"uredi-Hajnal}


There are $n$ men and $n$ women,
all of different handsomeness and beauty respectively,
and $m$ (heterosexual) {\it love affairs} ($0 \leq m \leq n^2$).
Fix $k$ and a permutation $\pi$ of size $k$. We
want to avoid the {\it love-pattern} $\pi$, i.e.
we forbid that there exist $k$ men and $k$ women such that,
for $i=1, \dots , k$, the $i$-th most handsome man
(amongst these $k$ men) loves the $\pi(i)$-th prettiest
woman (amongst these $k$ women).
{\bf Zolt\'an F\"uredi} and {\bf P\'eter Hajnal} 
conjectured that $m \leq C_k \cdot n$, for some constant $C_k$.
Here is the {\bf Marcus-Tardos} brilliant proof, that only uses
{\bf modularity} and {\bf pigeon-hole} (two times!).

Fix a love-pattern $\pi$ of size $k$, and let $f(n)$ be the
maximum number of love affairs for which you can still
avoid $\pi$. We want to find a {\it linear} upper bound for $f(n)$
(of course, trivially $f(n) \leq n^2$).
Let $n$ be divisible by $a$.

The first brilliant idea was to partition the men and the women into $n/a$ clubs where
the $a$ most handsome men belong to the first club,
the next $a$ most handsome men belong to the second club, etc.
and ditto for the women. 
A club {\it Loves} a club of the opposite sex
if there is at least one love affair between their members.

In order to find an upper bound for $f(n)$, the total number of
love affairs between individuals, all we need to know
an {\bf upper bound} for the number of {\it Loving clubs-pairs}, and 
an upper bound for the number of individual love-affairs possible
between any {\bf one  particlar} man's club, and any one
{\bf one  particlar} women's club (that it Loves).
There are $\leq f(n/a)$ pairs of Loving club-pairs (or else a `meta-pattern'
would entail a pattern), and the number of love-affairs possible,
just between members of any two specific Loving clubs is, trivially $\leq a^2$.
So we get the {\bf divide-and-conquer} inequality
$$
f(n) \leq a^2 f(n/a) \quad,
$$
which immediately yields the {\bf upper bound} $f(n) \leq n^2$.
Correct, but {\bf not very impressive}.

Can we do any better? Well, the above crude analysis is analogous to trying
to find an upper bound for the total personal property in the US.
We first find an upper bound for the number of people in the US, say $2.5 \cdot 10^8$,
and then we find that the richest person, Bill Gates, has less than $\$4 \cdot 10^{10}$,
and we get that the total personal property is at least
$$
(2.5 \cdot 10^8) \times (\$ 4 \cdot 10^{10}) \, \leq \,  \$ 10^{19} \quad ,
$$
a true, but {\bf far from sharp}, upper bound.

We can get a more realistic upper bound by defining a {\bf millionaire} as someone
who has more than a million dollars, and look up (in google, say) how many millionaires there
are in the US. According to a quiz in the {\tt redif.com} site, there are $2.27 \cdot 10^6$
of them.
Now the number of non-millionaires is very close to the total population, so we can
still use the same number, and each non-millionaire has less than $\$10^6$.
As for the millionaires, we use the Bill Gates upper bound, and we now get
that the total personal property in the USA is at least
$$
(2.5 \cdot 10^8) \times \$ 10^6 +
(2.27 \cdot 10^6) \times (\$4 \cdot 10^{10}) \, \leq  \,  \$ 10^{17} \quad .
$$
Of course, we can find an even sharper upper bound by also bounding the number
of {\bf billionaires}, but let's stop here.

Going back to pairs of Loving clubs, it is true that they can have
up to $a^2$ love-affairs amongst their members, but can they be
too many {\bf rich-in-love-affairs} club-pairs?

The second {\bf brilliant idea} of Adam Marcus and Gabor Tardos was to
define the analog of {\bf millionaire} for {\bf pairs of Loving clubs}.

A club {\it Adores} a club of the opposite sex
if there are at least $k$ members of the former club who
love someone in the latter club. 

Note that unlike `Love', `Adore' is not symmetric, since it may very well be that, 
e.g., $k$ men of the Adoring club
all have a crush on the same woman in the Adored women's-club.

It turns out that 
any one given club can't afford to Adore too many clubs of the
opposite sex, without the {\bf  forbidden love-pattern popping up}, for the following 
reason.

Whenever a men's club Adores a women's club it is thanks to
a certain set of $k$ men. Now any such set of $k$ men can't be
responsible for Adoring more than $k-1$ different women's-clubs, since otherwise
{\bf all love patterns} will show up, in particular the
{\bf forbidden} one! Similarly for womens clubs  Adoring men's clubs.
Hence (by {\bf pigeonhole!}),
there are $\leq k{ {a} \choose {k}}\cdot 2{{n} \over {a}}$
Adoring Pairs (of clubs, from either end).

So there can't be too many Adoring club-pairs. What about
a {\bf Loving but  non-Adoring} pair of clubs? Adam and Gabor claim
that they are {\bf poor-in-love-affairs}, in fact
the number of love affairs between their members
is $\leq (k-1)^2$, by {\bf pigeonhole} once again!
Indeed, there can be at most $k-1$ men who love {\it anyone} in
the other club (or else it would be Adoring), and each of these
men can love at most $k-1$ women in the Loved women's club
(or else the men's club will be Adored by the women's club).
So altogether, there can be at most $(k-1)^2$ love affairs
between these two Loving-but-non-Adoring club-pair.

Now we have the {\bf more refined} {\bf divide-and-conquer} inequality
$$
f(n) \,  \leq \,  f( {  {n} \over {a}}) \cdot  (k-1)^2 
\, + \, k{ {a} \choose {k}} {{2n} \over {a}} \cdot a^2 \quad ,
$$
which simplifies to
$$
f(n) \, \leq \, (k-1)^2 \cdot f( {  {n} \over {a}})+2ka{ {a} \choose {k}} \cdot n  \quad ,
$$
that immediately entails
$$
f(n) \leq {{2a^2 k { {a} \choose {k}} } \over {a-(k-1)^2}} \cdot n \quad.
$$
Now take any $a \geq (k-1)^2+1$. Marcus and Tardos
took $a=k^2$, getting $C_k=2k^4{ {k^2} \choose {k}}$. \halmos

{\bf Martin Klazar} showed, in 2000, that {\bf F\"uredi-Hajnal} implies 
{\bf Stanley-Wilf}. It will take me another two minutes to describe it,
but I hate to go overtime, so just look at the handout I gave you, or
search google for {\bf ``Marcus-Tardos''} and you will see it right away.
Thanks so much!

\end

