A Loving Rendition of the Marcus-Tardos Amazing Proof of the Furedi-Hajnal Conjecture

By Doron Zeilberger

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!

(Plain ) .tex version (1 page)

.dvi version (for previewing)

.ps version

.pdf version

Added Dec. 3, 2003: This gem inspired Doron Zeilberger's Opinion 58

The Personal Journal of Ekhad and Zeilberger

Doron Zeilberger's List of Other Papers

Doron Zeilberger's Home Page