Kombinatorika matic bez zakázaných vzorů

Mikšaník, David

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

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři