2025/10/31 by Lei Cao, Cao, Lei, Tsai, Shen-Fu
Computer Science · Mathematics · #05D99 #Advanced Combinatorial Mathematics #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2510.27076
openalex publication_date 2025/10/31 · openalex created_date 2025/11/05 · openalex updated_date 2026/07/28
We introduce two related notions of pattern enforcement in (0,1)-matrices: Q-forcing and strongly Q-forcing, which formalize distinct ways a fixed pattern Q must appear within a larger matrix. A matrix is Q-forcing if every submatrix can realize Q after turning any number of 1-entries into 0-entries, and strongly Q-forcing if every 1-entry belongs to a copy of Q. For Q-forcing matrices, we establish the existence and uniqueness of extremal constructions minimizing the number of 1-entries, characterize them using Young diagrams and corner functions, and derive explicit formulas and monotonicity results. For strongly Q-forcing matrices, we show that the minimum possible number of 0-entries of an m× n strongly Q-forcing matrix is always O(m+n), determine the maximum possible number of 1-entries of an n× n strongly P-forcing matrix for every 2×2 and 3×3 permutation matrix, and identify symmetry classes with identical extremal behavior. We further propose a conjectural formula for the maximum possible number of 1-entries of an n× n strongly Ik-forcing matrix, supported by results for k=2,3. These findings reveal contrasting extremal structures between forcing and strongly forcing, extending the combinatorial understanding of pattern embedding in (0,1)-matrices.