2020/12/29 by Benjamin Aram Berendsohn, Berendsohn, Benjamin Aram
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.14717
openalex publication_date 2020/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 sat(P,n) for a 0-1 matrix pattern P indicates the minimum number of 1s in a n × 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 the saturation function is either bounded or in Θ(n). Building on their results, we find a large class of patterns with bounded saturation function, including both infinitely many permutation matrices and infinitely many non-permutation matrices.