Problems around the Stanley-Wilf Limits of Permutation

Abstract

The Theory of Matrix Avoidance explores the problem of determining the maximum number of 1-entries in an 𝑛 × 𝑛 binary matrix that avoids a fixed pattern 𝑃. For permutation matrices, the Furedi-Hajnal conjecture posits a linear relationship between this number, known as extremal function of 𝑛, and the matrix size 𝑛. This conjecture was initially proven by Marcus and Tardos, and subsequently, the linear constant was further improved.

Another class of matrices, known as light matrices, exhibits a quasi-linear extremal function. Although, the proof for this class relies on the connection between pattern avoidance and the theory of Davenport-Schinzel sequences. This thesis presents a proof for light matrices in terms of matrices without applying known results from connected topics, followed by an alternative proof for the Furedi-Hajnal conjecture. By addressing these topics, this research contributes to the understanding of matrix avoidance and its implications for different matrix classes.