2017/04/18 by P. A. CrowdMath, CrowdMath, P. A.
Computer Science · Engineering · #05D99 #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1704.05207
openalex publication_date 2017/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say a zero-one matrix A avoids another zero-one matrix P if no submatrix of A can be transformed to P by changing some ones to zeros. A fundamental problem is to study the extremal function ex(n,P), the maximum number of nonzero entries in an n × n zero-one matrix A which avoids P. To calculate exact values of ex(n,P) for specific values of n, we need containment algorithms which tell us whether a given n × n matrix A contains a given pattern matrix P. In this paper, we present optimal algorithms to determine when an n × n matrix A contains a given pattern P when P is a column of all ones, an identity matrix, a tuple identity matrix, an L-shaped pattern, or a cross pattern. These algorithms run in Θ(n2) time, which is the lowest possible order a containment algorithm can achieve. When P is a rectangular all-ones matrix, we also obtain an improved running time algorithm, albeit with a higher order.