Combinatorial Theory

A 0-1 matrix \(M\) contains a 0-1 matrix pattern \(P\) if we can obtain \(P\) from \(M\) by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function \(\mathrm{sat}(P,n)\) for a 0-1 matrix pattern \(P\) indicates the minimum number of 1s in an \(n \times n\) 0-1 matrix that does not contain \(P\), but changing any 0-entry into a 1-entry creates an occurrence of \(P\). Fulek and Keszegh recently showed that each pattern has a saturation function either in \(\mathcal{O}(1)\) or in \(\Theta(n)\). We fully classify the saturation functions of permutation matrices.

Mathematics Subject Classifications: 05D99

Keywords: Forbidden submatrices, saturation