On constants in the Füredi–Hajnal and the Stanley–Wilf conjecture

For a given permutation matrix P, let fP(n) be the maximum number of 1-entries in an n×n (0,1)-matrix avoiding P and let SP(n) be the set of all n×n permutation matrices avoiding P. The Füredi–Hajnal conjecture asserts that cP:=limn→∞fP(n)/n is finite, while the Stanley–Wilf conjecture asserts that 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 (sP) and the Füredi–Hajnal limit (cP). We improve the reduction and obtain which decreases the general upper bound on sP from sP⩽constconstO(klog(k)) to sP⩽constO(klog(k)) for any k×k permutation matrix P. In the opposite direction, we show .For a lower bound, we present for each k a k×k permutation matrix satisfying cP=Ω(k2).