Minimal k-Blockers of 123-Avoiding Permutation Matrices
Abstract
We investigate n × n (0, 1)-matrices A that avoid σk, where σk is the permutation {1, 2,…, k}, and we focus on 123-avoiding permutations. A k-blocker of 123-avoiding permutation matrices is a set of positions in an n × n matrix that intersect each 123-avoiding permutation matrix at least k times. The Hankel cyclic decomposition implies that each k-blockers must have cardinality at least kn. The dimensions of the k-blockers of all permutation matrices are determined by Fulkerson’s generalization of the Frobenius-König theorem: any r × s submatrix is a k-blocker of all permutation matrices if r + s = n + k. We investigate the properties of these minimal blockers as elements are shifted certain horizontal Hankel-cyclic distances. We have found minimal blockers in shapes not given by Fulkerson’s result, and we explore and characterize these minimal k-blockers.
Faculty Sponsors
Dr. Lei Cao
Project Type
Event
Location
Alvin Sherman Library
Start Date
4-6-2022 12:00 PM
End Date
4-7-2022 5:00 PM
Minimal k-Blockers of 123-Avoiding Permutation Matrices
Alvin Sherman Library
We investigate n × n (0, 1)-matrices A that avoid σk, where σk is the permutation {1, 2,…, k}, and we focus on 123-avoiding permutations. A k-blocker of 123-avoiding permutation matrices is a set of positions in an n × n matrix that intersect each 123-avoiding permutation matrix at least k times. The Hankel cyclic decomposition implies that each k-blockers must have cardinality at least kn. The dimensions of the k-blockers of all permutation matrices are determined by Fulkerson’s generalization of the Frobenius-König theorem: any r × s submatrix is a k-blocker of all permutation matrices if r + s = n + k. We investigate the properties of these minimal blockers as elements are shifted certain horizontal Hankel-cyclic distances. We have found minimal blockers in shapes not given by Fulkerson’s result, and we explore and characterize these minimal k-blockers.
