Extensions of the linear bound in the Füredi-Hajnal conjecture

Abstract

In 2004 Marcus and Tardos proved that every n by n matrix that has entries 1 and 0 and avoids a fixed permutation matrix as a submatrix, has only O(n) entries 1. We extend this result to higher dimensional matrices and to hypergraphs.

Keywords

• Extensions
• linear
• bound
• Füredi-Hajnal
• conjecture