This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and earlier selections, see this post.
My choice for 2003 in combinatorics is the proof by Marcus and Tardos of the famous Stanley–Wilf conjecture, which states that the growth rate of every proper permutation class is singly exponential. The paper was submitted in 2003 and published in 2004 (Marcus and Tardos 2004).
A permutation of is called an -permutation. We say that an -permutation contains a -permutation if there exist integers such that for all we have if and only if . Otherwise, we say that avoids . For a fixed permutation , let be the number of -permutations avoiding . In the late 1980s, Stanley and Wilf (Wilf 1993) conjectured that for all there exists a constant such that for all .
In 2000, Klazar (Klazar 2000) proved that this conjecture would follow from a conjecture of F"uredi and Hajnal about permutation matrices. Let and be - matrices (that is, matrices with all entries or ). We say that contains the matrix with entries if there exists a submatrix of with entries such that whenever . Otherwise we say that avoids . Let be the maximum number of -entries in an - matrix avoiding . A - matrix P is called a permutation matrix if it has exactly one entry of in each row and each column and s elsewhere. In 1992, F"uredi and Hajnal (Füredi and Hajnal 1992) conjectured that grows at most linearly in . In 2004, Marcus and Tardos (Marcus and Tardos 2004) proved this conjecture.
The proof of Theorem is surprisingly simple. The authors used a partitioning of the larger matrix into blocks to prove a linear recursion for , from which the theorem follows easily. Together with the result of Klazar (Klazar 2000), Theorem implies the truth of the Stanley–Wilf conjecture.
Theorem became a cornerstone for many subsequent developments, one of which we describe below. In 2006, Balogh, Bollob’as and Morris (Balogh et al. 2006) formulated a far-reaching generalization of the Stanley–Wilf conjecture. An ordered graph is a graph (without loops or multiple edges) together with a total order on its vertices. A collection of ordered graphs is called a property if it is closed under order-preserving isomorphisms of the vertex set. We will write for the number of non-isomorphic ordered graphs on vertices in . A property of ordered graphs is called hereditary if it is closed under taking induced sub-graphs (with the induced ordering). Balogh, Bollob’as and Morris (Balogh et al. 2006) conjectured that for every hereditary property of ordered graphs, the function either has at most exponential growth, or has at least factorial growth. In 2024, Bonnet et al. (Bonnet et al. 2024) confirmed this conjecture.
The ordered permutation graph associated to a permutation of is the ordered graph with vertices ordered as , such that two vertices are adjacent if and only if . The Stanley–Wilf conjecture corresponds to the special case of Theorem when all graphs in are ordered permutation graphs.