Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

An exact characterization of saturation for permutation matrices

Published Web Location Commons 'BY' version 4.0 license

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View