Exclusive for the Personal Journal of Ekhad and Zeilberger
Written: Nov. 30, 2003
Just because a conjecture has been posed by brilliant people, and attempted, unsuccesfuly, by quite a few other brilliant people, does not mean that the ultimate proof has to be complicated. We saw this a year ago with the AKS Primality is P result, and now the brilliant proof of the Füredi-Hajnal conjecture, and hence the Stanley-Wilf conjecture by "0-th year grad student" Adam Marcus (now at GA Tech) and Gabor Tardos. Once I saw their proof, I kicked myself, as I am sure did many other people. Once you see it is so NATURAL and "obvious". But if it is so "obvious", how come no one (including myself) did come up with it? So like most of the truly great discoveries, it is aposteriori `obvious', but definitely not `a priori'.
Such a beautiful proof deserves a beautiful exposition, and this is what I did in this one-page paper, where I replaced the cold and alienating "rows" and "columns" by lively men and women who fall in love, and form clubs, rather than "blocks", and Adore each other rather than being "wide" and/or "tall". I hope that you will enjoy the brilliant Marcus-Tardos proof as much as I did!
The Personal Journal of Ekhad and Zeilberger
Doron Zeilberger's List of Other Papers