Minimum Blockers of 123-Avoiding Permutation Matrices
Abstract
A blocker of �� × �� permutation matrices is a set of positions in an �� × �� matrix that intersects each permutation matrix at least once. A blocker is minimum if removing any position makes it no longer a blocker. The Hankel cyclic decomposition implies that each minimum blocker of 123-avoiding permutation matrices must have a cardinality of at least ��, and minimum blockers containing exactly �� positions are called minimal blockers. The well-known Frobenius-König theorem characterizes the minimal blockers of permutation matrices: any �� × �� submatrix is a minimal blocker of all permutation matrices if and only if �� + �� = �� + 1.
Recently, Brualdi and Cao characterized the minimal blockers of 123-avoiding permutation matrices, focusing on L-shaped blockers. We continue their study by defining minimum flag-shaped blockers, which we show are generalizations of L-shaped blockers. We investigate the upper and lower bounds of the dimensions of faces, determined by the minimum blockers, of the polytope generated by 123- avoiding permutation matrices.
Faculty Sponsors
Dr. Lei Cao
Project Type
Event
Location
Alvin Sherman Library
Start Date
4-5-2023 12:00 PM
End Date
4-6-2023 4:00 PM
Minimum Blockers of 123-Avoiding Permutation Matrices
Alvin Sherman Library
A blocker of �� × �� permutation matrices is a set of positions in an �� × �� matrix that intersects each permutation matrix at least once. A blocker is minimum if removing any position makes it no longer a blocker. The Hankel cyclic decomposition implies that each minimum blocker of 123-avoiding permutation matrices must have a cardinality of at least ��, and minimum blockers containing exactly �� positions are called minimal blockers. The well-known Frobenius-König theorem characterizes the minimal blockers of permutation matrices: any �� × �� submatrix is a minimal blocker of all permutation matrices if and only if �� + �� = �� + 1.
Recently, Brualdi and Cao characterized the minimal blockers of 123-avoiding permutation matrices, focusing on L-shaped blockers. We continue their study by defining minimum flag-shaped blockers, which we show are generalizations of L-shaped blockers. We investigate the upper and lower bounds of the dimensions of faces, determined by the minimum blockers, of the polytope generated by 123- avoiding permutation matrices.
