
In Any Way but This. Pattern Avoidance. The Basics. 177
4.5 The Proof of the Stanley-Wilf Conjecture
The goal of this section is to present a proof of the Stanley–Wilf conjecture.
In order to achieve this goal, we will discuss one more conjecture involving
0-1 matrices, show why it implies the Stanley–Wilf conjecture, and then prove
the conjecture on the 0-1 matrices. The proof we present was announced by
Adam Marcus and G´abor Tardos in the Fall of 2003. Before that, Noga Alon
and Ehud Friedgut [9] proved a somewhat weaker result.
4.5.1 The F¨uredi–Hajnal Conjecture
Let us extend the notion of pattern avoidance to 0-1 matrices as follows.
DEFINITION ...