Extensions of the linear bound in the Furedi-Hajnal conjecture

Details Extensions of the linear bound in the Furedi-Hajnal conjecture Extensions of the linear bound in the Furedi-Hajnal conjecture

2005-07-08

arxiv.org/abs/math/0507164v1

Mathematics

Combinatorics

11 pages

Scientific paper

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 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 Branden and Mansour.We then extend the original Furedi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1's in a d-dimensional 0-1 matrix with side length n which avoids a d-dimensional permutation matrix is O(n^{d-1}).

Affiliated with

Also associated with

No associations

Rating

Extensions of the linear bound in the Furedi-Hajnal conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extensions of the linear bound in the Furedi-Hajnal conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extensions of the linear bound in the Furedi-Hajnal conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375016