Stanley–Wilf conjecture

Remarks

The conjecture was proved by Adam Marcus and Gábor Tardos in 2004. They proved the Füredi–Hajnal conjecture on $0$-$1$ matrices that avoid a permutation matrix, and Martin Klazar had shown earlier that it implies the Stanley–Wilf conjecture. The bound means that the limit $L(\sigma) = \lim_{n \to \infty} \abs{\operatorname{Av}_n(\sigma)}^{1/n}$ is finite; Arratia showed that this limit exists. The number $L(\sigma)$ is the Stanley–Wilf limit of $\sigma$.

Example: for $\sigma = 123$, $\abs{\operatorname{Av}_n(123)}$ is the Catalan number $C_n \le 4^n$, so $c_{123} = 4$ works and $L(123) = 4$.

Without a forbidden pattern the statement fails, since there are $n!$ permutations of $\set{1, \ldots, n}$, and $n!$ grows faster than $c^n$ for each constant $c$.

Going deeper

For a student

For patterns of length $3$ the counts are Catalan numbers, but for longer patterns exact formulas are rare. The theorem says that every pattern class has finite exponential growth rate, the Stanley–Wilf limit. The proof by Marcus and Tardos is short and goes through extremal problems for $0$-$1$ matrices.