A Loving Rendition of the Marcus-Tardos Amazing Proof of the Füredi-Hajnal Conjecture

Doron ZEILBERGER ^{1}

There are n men and n women, all of different handsomeness and beauty respectively, and m (heterosexual) love affairs (0 ≤ m ≤ n^{2}). Fix k and a permutation π of size k. We want to avoid the love-pattern π, i.e. we forbid that there exist k men and k women such that, for i = 1, …, k, the i-th most handsome man (amongst these k men) loves the π(i)-th prettiest woman (amongst these k women). Zoltán Füredi and Péter Hajnal (Discrete Math 103 (1992), 233-251) conjectured that m ≤ C_{k} · n, for some constant C_{k}. Adam MARCUS and Gábor TARDOS (preprint, available from http://www.renyi.hu/˜ tardos/) have just proven it. I love their proof so much that I decided to rephrase it in the evocative language of love.

Fix a love-pattern π of size k, and let f(n) be the maximum number of love affairs for which you can still avoid π. 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 Loves a club of the opposite sex if there is at least one love affair between their members. A club 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 ≤ f(n/a) (or else a “meta-pattern” would yield a pattern). A club can Adore at most k\binom{a}{k} clubs of the opposite sex, since otherwise (pigeonhole!) there would be ≥ k Adored clubs who get Adored thanks to the same k members of one of the \binom{a}{k} k-subsets of the Adoring club, thereby containing any love-pattern of size k, in particular π. Hence there are ≤ k\binom{a}{k} · 2\frac{n}{a} Adoring Pairs (of clubs, from either end). The number of love affairs between members of Loving but non-Adoring clubs is ≤ (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) ≤ a^{2}. This implies the divide-and conquer inequality f(n) ≤ (k − 1)^{2} · f(\frac{n}{a}) + 2ak\binom{a}{k} · n, that entails f(n) ≤ \frac{2a^{2}k\binom{a}{k}}{a−(k−1)^{2}} · n. Now take any a ≥ (k − 1)^{2} + 1. Marcus and Tardos took a = k^{2}, getting C_{k} = 2k^{4}\binom{k^{2}}{k}.

Thanks to Martin Klazar (FPSAC 2000, 250-255), the Stanley-Wilf conjecture is an immediate corollary. Let F (n) be the number of love-configurations avoiding π. Now partition the men and women into “clubs” of size 2. We have F (n) ≤ F (n/2)·15^{C_{k}·n/2} (deciding the love-configuration for the clubs, and which of the 2^{4} − 1 love-configurations between each of the ≤ C_{k} · n/2 Loving Pairs). This implies F (n) ≤ 15^{C_{k}·n}, hence F (n) is of exponential growth.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. http://www.math.rutgers.edu/~zeilberg/ . Nov. 28, 2003. Exclusive to the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html . Supported in part by the NSF. Thanks are due to Miklos Bona, Tim Chow, and Vince Vatter for helpful discussions.