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

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 exponenti...

Full description

Saved in:
Bibliographic Details
Published in:Advances in applied mathematics 2007-02, Vol.38 (2), p.258-266
Main Authors: Klazar, Martin, Marcus, Adam
Format: Article
Language:English
Subjects:
[formula omitted]-Matrix
Algebraic combinatorics
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Extremal theory
Graph theory
Mathematics
Ordered hypergraph
Sciences and techniques of general use
Stanley–Wilf conjecture
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ( n d − 1 ) .
ISSN:0196-8858
1090-2074
DOI:10.1016/j.aam.2006.05.002