Abstract
For a given permutation matrix P, let f_P(n) be the maximum number of 1-entries in an nxn (0,1)-matrix avoiding P and let S_P(n) be the set of all nxn permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that c(P):=lim(n--}infinity) f_P(n)/n is finite, while the Stanley-Wilf conjecture asserts that s(P):=lim(n--}infinity) n-th root of S_P(n) is finite.
In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture. We focus on the values of the Stanley-Wilf limit (s(P)) and the Füredi-Hajnal limit (c(P)).
We improve the reduction and obtain s(P){=2.88c(P)^2 which decreases the general upper bound on s(P) from s(P){=const^(const^(klog(k))) to s(P){=const^(klog(k)) for any kxk permutation matrix P. In the opposite direction, we show c(P)=O(s(P)^4.5).
For a lower bound, we present for each k a kxk permutation matrix satisfying c(P)=Omega(k^2).