TY - JOUR

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

AU - Klazar, Martin

AU - Marcus, Adam

N1 - Funding Information:
* Corresponding author. E-mail addresses: [email protected] (M. Klazar), [email protected] (A. Marcus). 1 ITI is supported by the project 1M0021620808 of the Czech Ministry of Education. 2 Research performed as Visiting Researcher at Alfréd Rényi Institute, Hungary. This research was made possible by the Fulbright Program in Hungary.

PY - 2007/2

Y1 - 2007/2

N2 - We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1-entries in an n × n(0, 1) -matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Brändén and Mansour. We then extend the original Füredi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1-entries in a d-dimensional (0, 1)-matrix with side length n which avoids a d-dimensional permutation matrix is O (nd - 1).

AB - We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1-entries in an n × n(0, 1) -matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Brändén and Mansour. We then extend the original Füredi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1-entries in a d-dimensional (0, 1)-matrix with side length n which avoids a d-dimensional permutation matrix is O (nd - 1).

KW - (0, 1)-Matrix

KW - Extremal theory

KW - Ordered hypergraph

KW - Stanley-Wilf conjecture

UR - http://www.scopus.com/inward/record.url?scp=33751014065&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33751014065&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2006.05.002

DO - 10.1016/j.aam.2006.05.002

M3 - Article

AN - SCOPUS:33751014065

SN - 0196-8858

VL - 38

SP - 258

EP - 266

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 2

ER -