12⋯t-Permutation Avoiding (0, 1)-Matrices

Let n and t be integers with 1<t≤n. Let A be an n×n (0, 1)-matrix with a positive permanent, that is, for which there exists a permutation matrix P≤A (entrywise order). We investigate the minimum number α(n,t) of zeros possible in such a matrix A which avoids a P with a 12⋯t-pattern, that is, for which there does not exist a permutation matrix P≤A containing the identity matrix It as a submatrix. We conjecture that α(n,t)=k+12 where k=n-t+1. We prove this conjecture is correct when t=2or3 and we consider for which matrices equality holds. We also prove the conjecture is correct for all t if n≥2k-3. Finally, we investigate which 12⋯t-permutation avoiding matrices have the maximum permanent.