123-Forcing matrices

Authors

Richard A. Brualdi, University of Wisconsin
Lei Cao, Nova Southeastern UniversityFollow

Document Type

Article

Publication Date

2023

Publication Title

Australasian Journal of Combinatorics

ISSN

2202-3518

Volume

86

Issue/No.

1

First Page

169

Last Page

186

Abstract

A permutation σ of {1, 2,...,n} contains a 123-pattern provided it contains an increasing subsequence of length 3 and, otherwise, is 123-avoiding. In terms of the n × n permutation matrix P corresponding to σ, P contains a 123-pattern provided the 3 × 3 identity matrix I3 is a submatrix of P. If A is an n × n (0, 1)-matrix, then A is 123-forcing provided every permutation matrix P ≤ A contains a 123-pattern. The main purpose of this paper is to characterize such matrices A with the minimum number of 0’s.

Comments

© The author(s).

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

NSUWorks Citation

Brualdi, Richard A. and Cao, Lei, "123-Forcing matrices" (2023). Mathematics Faculty Articles. 361.
https://nsuworks.nova.edu/math_facarticles/361

ORCID ID

0000-0001-7613-7191