Open Access Publications from the University of California

## Published Web Location

https://doi.org/10.5070/C63160430
Abstract

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