Problems around the Stanley-Wilf Limits of Permutation

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2023-08-22
Department
Major/Subject
Applied Mathematics
Mcode
SCI3053
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
47
Series
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.
Description
Supervisor
Chalermsook, Parinya
Thesis advisor
Yingchareonthawornchai, Sorrachai
Keywords
permutation avoidance, forbidden matrix, Stanley-Wilf limit, Furedi-Hajnal limit, light matrix
Other note
Citation