Abstrakt
Pro danou permutační matici P značíme jako f_P(n) největší možný počet jedniček v n x n (0,1)-matici, která neobsahuje P jako podmatici a jako S_P(n) množinu všech n x n permutačních matic neobsahujících P. Fürediho-Hajnalova domněnka říká, že c(P) := lim(n--}infinity) f_P(n)/n je konečná a Stanleyho-Wilfova domněnka, že s(P) := lim(n--}infinity) n-tá odmocnina S_P(n) je konečná.
Marcus s Tardosem dokázali Fürediho-Hajnalovu domněnku v roce 2004, která přes Klazarovu redukci z roku 2000 dokazuje Stanleyho-Wilfovu domněnku. Článek se zabývá hodnotami Stanleyho-Wilfovy limity (s(P)) a Fürediho-Hajnalovy limity (c(P)). Zlepšením redukce dostáváme s(P) {= 2.88c(P)^2, což snižuje horní odhad na s(P) z s(P) {= const^(const^(klog(k))) na s(P) {= const^(klog(k)) pro libovolnou k x k permutační matici P.
Pro opačný směr ukážeme c(P) = O(s(P)^4.5). Dále pro každé k najdeme k x k permutační matici s c(P) = Omega(k^2).