|
|
The combinatorics of pattern-avoiding matrices
Mikšaník, David ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
A permutation matrix P partially avoids a quasi-permutation matrix A (i.e., a 01- matrix such that each column and row of A contains at most one nonzero entry) if there is no submatrix P′ of P of the same size as A satisfying Ai,j ≤ P′ i,j for all possible indices i and j. Two quasi-permutation matrices A and B are partially Wilf-equivalent if, for every n ∈ N, the number of permutation matrices of order n partially avoiding A is the same as the number of permutation matrices of order n partially avoiding B. This generalizes the well-known concept of avoidance and Wilf equivalence of permutations. One of the central topics in this area is the classification of permutations of order k into Wilf equivalence classes. The complete classification is known for k = 1, 2, . . . , 7. In our thesis, we study the same problem for quasi-permutation matrices. Namely, we classify all 371 quasi-permutation matrices of size at most 4 × 4 into partial Wilf equivalence classes (two quasi-permutation matrices belong to the same class if and only if they are partially Wilf-equivalent). Along the way, we prove several general results showing how to construct from one or two quasi-permutation matrices more quasi-permutation matrices that are pairwise partially Wilf-equivalent. 1
|
guest ::
