Blockers of pattern avoiding permutation matrices

We investigate n × n (0, 1)-matrices A such that no permutation matrix P ≤ A belongs to a prescribed subset Q_n of the set P_n of all n × n permutation matrices. The subsets Q_n considered are those defined by avoiding a given pattern σ_k where σ_k is a permutation of {1, 2, …, k}. This gives rise to consideration of (minimal) blockers which are certain subsets of the positions of an n × n matrix that intersect every permutation matrix that avoids the pattern σ. The classical case is that where Q_n = P_n and thus our investigations can be viewed as a generalization of the well-known Frobenius-König theorem. By this theorem the positions of any r × s submatrix with r + s = n + 1 is a minimal blocker of P_n; in particular rows and columns are not only minimal blockers but are minimum cardinality blockers; the maximum size of a minimal blocker occurs when r and s are (nearly) equal. The case k = 3 is considered in some detail. In case k ≥ 4, we show that every minimum blocker for any given pattern σ_k with cardinality equal to n is a row or column.