Extremal functions of forbidden double permutation matrices

We say a 0–1 matrix A avoids a matrix P if no submatrix of A can be transformed into P by changing some ones to zeroes. We call P an m-tuple permutation matrix if P can be obtained by replacing each column of a permutation matrix with m copies of that column. In this paper, we investigate n × n matrices that avoid P and the maximum number ex ( n , P ) of ones that they can have. We prove a linear bound on ex ( n , P ) for any 2-tuple permutation matrix P, resolving a conjecture of Keszegh [B. Keszegh, On linear forbidden matrices, J. Combin. Theory Ser. A 116 (1) (2009) 232–241]. Using this result, we obtain a linear bound on ex ( n , P ) for any m-tuple permutation matrix P. Additionally, we demonstrate the existence of infinitely many minimal non-linear patterns, resolving another conjecture of Keszegh from the same paper.