Typical growth of the Füredi-Hajnal and Stanley-Wilf limits

Abstract

We prove that the Füredi-Hajnal limit and the Stanley-Wilf limit of a uniformly random permutation matrix of order $k$ are at most $\exp (O(\sqrt{k}(\log k{)}^{5/2}))$ with probability tending to one as $k\to \infty$. This improves the bound $\exp (O(k^{2/3}(\log k{)}^{7/3}/(\log \log k{)}^{1/3}))$ of Cibulka and Kynčl. Together with the lower bound due to Fox, these bounds show that the logarithms of both limits are $k^{1/2+o(1)}$ for almost all permutations.