Extensions of the linear bound in the Furedi-Hajnal conjecture

Martin Klazar, Adam Marcus

We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1's in an n by n 0-1 matrix avoiding a fixed permutation matrix. We first extend the linea…