Abstract
A binary matrix is a matrix with entries from the set {0,1}. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries.
If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k x k matrix with exactly one 1-entry in every row and one 1-entry in every column.
The Füredi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant c_P such that for every positive integer n, every n times n binary matrix A with at least c_Pn 1-entries contains P. We show that c_P<=2^O(k^{2/3} log^{7/3} k/(log log k)^{1/3}) asymptotically almost surely for a random k-permutation matrix P.
We also show that c_P<=2^{(4+o(1))k} for every k-permutation matrix P, improving the constant in the exponent of a recent upper bound on c_P by Fox. We also consider a higher-dimensional generalization of the Stanley-Wilf conjecture about the number of d-dimensional n-permutation matrices avoiding a fixed d-dimensional k-permutation matrix, and prove almost matching upper and lower bounds of the form (2^k)^O(n) (n!)^{d-1-1/(d-1)} and n^{-O(k)} k^Omega(n) (n!)^{d-1-1/(d-1)}, respectively.