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

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\mathrm{/}2}))$ with probability tending to one as $k\to \mathrm{\infty }$. This improves the bound $\exp (O(k^{2\mathrm{/}3}(\log k{)}^{7\mathrm{/}3}\mathrm{/}(\log \log k{)}^{1\mathrm{/}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\mathrm{/}2+o(1)}$ for almost all permutations.