%martar.tex: ``A Loving Rendition of the Marcus-Tardos Amazing Proof
%of the Furedi-Hajnal Conjecture''
%
%a Plain TeX file by Doron Zeilberger (1 page)
%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
%end macros
\bf
\centerline
{A Loving Rendition of the Marcus-Tardos Amazing Proof
of the F\"uredi-Hajnal Conjecture
}
\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.
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/ .}
Nov. 28, 2003.
Exclusive to the Personal Journal of Ekhad and Zeilberger
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html .}
Supported in part by the NSF. Thanks are due to Miklos Bona, Tim Chow,
and Vince Vatter for helpful discussions.
}
}
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} ({\bf Discrete Math 103 (1992), 233-251})
conjectured that $m \leq C_k \cdot n$, for some constant $C_k$.
{\bf Adam MARCUS} and {\bf G\'abor TARDOS}
(preprint, available from {\bf http://www.renyi.hu/\Tilde tardos/})
have just proven it.
I love their proof so much that I decided to
rephrase it in the evocative language of {\bf love}.
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$. Let $n$ be divisible by $a$.
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.
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.
The total number of Loving Pairs amongst the $n/a$ men- and women-
clubs is $\leq f(n/a)$
(or else a ``meta-pattern" would yield
a pattern). A club can Adore
at most $k { {a} \choose {k}}$ clubs of the opposite sex,
since otherwise ({\bf pigeonhole!})
there would be $\geq k$ Adored clubs who get Adored thanks
to the {\it same} $k$ members of
{\it one} of the ${ {a} \choose {k}}$ $k$-subsets of the Adoring club,
thereby containing {\it any} love-pattern of size $k$,
in particular $\pi$.
Hence there are $\leq k{ {a} \choose {k}}\cdot 2{{n} \over {a}}$
Adoring Pairs (of clubs, from either end).
The number of love affairs between members
of Loving but non-Adoring clubs is
$\leq (k-1)^2$ (or else there would be at least $k$ persons
in one of these two clubs who love people in the other club),
and the number of love affairs between Adoring clubs is
(trivially) $\leq a^2$. This implies the
{\bf divide-and conquer} inequality
$f(n) \leq (k-1)^2 \cdot f( { {n} \over {a}})+2ak{ {a} \choose {k}} \cdot n$,
that entails
$f(n) \leq {{2a^2k{ {a} \choose {k}} } \over {a-(k-1)^2}} \cdot n$.
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
Thanks to {\bf Martin Klazar} ({\bf FPSAC 2000, 250-255}),
the {\bf Stanley-Wilf} conjecture is an immediate corollary.
Let $F(n)$ be the number of love-configurations avoiding $\pi$.
Now partition the men and women into ``clubs'' of size $2$.
We have $F(n) \leq F(n/2) \cdot 15^{C_k \cdot n/2}$ (deciding the
love-configuration for the clubs, and which of the $2^4-1$
love-configurations between each of the $\leq C_k \cdot n/2$ Loving Pairs).
This implies $F(n)\leq 15^{C_k \cdot n}$, hence $F(n)$ is of exponential
growth.
\end