Almost all permutation matrices have bounded saturation functions

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

permutation matrices Saturation problems for forbidden graphs

Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Positive matrices and their generalizations; cones of matrices (15B48)

Abstract: Saturation problems for forbidden graphs have been a popular area of research for many decades, and recently Brualdi and Cao initiated the study of a saturation problem for 0-1 matrices. We say that 0-1 matrix

A

is saturating for the forbidden 0-1 matrix

P

if

A

avoids

P

but changing any zero to a one in

A

creates a copy of

P

. Define

s a t (n, P)

to be the minimum possible number of ones in an

n i m e s n

0-1 matrix that is saturating for

P

. Fulek and Keszegh proved that for every 0-1 matrix

P

, either

s a t (n, P) = O (1)

or

s a t (n, P) = T h e t a (n)

. They found two 0-1 matrices

P

for which

s a t (n, P) = O (1)

, as well as infinite families of 0-1 matrices

P

for which

s a t (n, P) = T h e t a (n)

. Their results imply that

s a t (n, P) = T h e t a (n)

for almost all

k i m e s k

0-1 matrices

P

. Fulek and Keszegh conjectured that there are many more 0-1 matrices

P

such that

s a t (n, P) = O (1)

besides the ones they found, and they asked for a characterization of all permutation matrices

P

such that

s a t (n, P) = O (1)

. We affirm their conjecture by proving that almost all

k i m e s k

permutation matrices

P

have

s a t (n, P) = O (1)

. We also make progress on the characterization problem, since our proof of the main result exhibits a family of permutation matrices with bounded saturation functions.

Review text

Summary: Saturation problems for forbidden graphs have been a popular area of research for many decades, and recently \textit{R. A. Brualdi} and \textit{L. Cao} [``Pattern-avoiding (0, 1)-matrices, Preprint, \url{arXiv:2005.00379}] initiated the study of a saturation problem for 0-1 matrices. We say that a 0-1 matrix \(A\) is saturating for the forbidden 0-1 matrix \(P\) if \(A\) avoids \(P\) but changing any zero to a one in \(A\) creates a copy of \(P\). Define \(\text{sat}(n, P)\) to be the minimum possible number of ones in an \(n \times n\) 0-1 matrix that is saturating for \(P\). \textit{R. Fulek} and \textit{B. Keszegh} [``Saturation problems about forbidden 0-1 submatrices, Preprint, \url{arXiv:2010.08256}] proved that for every 0-1 matrix \(P\), either \(\operatorname{sat}(n, P) = O(1)\) or \(\operatorname{sat}(n, P) = \Theta(n)\). They found two 0-1 matrices \(P\) for which \(\text{sat}(n, P) = O(1)\), as well as infinite families of 0-1 matrices \(P\) for which \(\operatorname{sat}(n, P) = \Theta(n)\). Their results imply that \(\text{sat}(n, P) = \Theta(n)\) for almost all \(k \times k\) 0-1 matrices \(P\). Fulek and Keszegh [loc. cit.] conjectured that there are many more 0-1 matrices \(P\) such that \(\operatorname{sat}(n, P) = O(1)\) besides the ones they found, and they asked for a characterization of all permutation matrices \(P\) such that \(\operatorname{sat}(n, P) = O(1)\). We affirm their conjecture by proving that almost all \(k \times k\) permutation matrices \(P\) have \(\operatorname{sat}(n, P) = O(1)\). We also make progress on the characterization problem, since our proof of the main result exhibits a family of permutation matrices with bounded saturation functions.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Almost all permutation matrices have bounded saturation functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831345)