### Abstract

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}).

Original language | English (US) |
---|---|

Pages (from-to) | 258-266 |

Number of pages | 9 |

Journal | Advances in Applied Mathematics |

Volume | 38 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1 2007 |

### All Science Journal Classification (ASJC) codes

- Applied Mathematics

### Keywords

- (0, 1)-Matrix
- Extremal theory
- Ordered hypergraph
- Stanley-Wilf conjecture

## Fingerprint Dive into the research topics of 'Extensions of the linear bound in the Füredi-Hajnal conjecture'. Together they form a unique fingerprint.

## Cite this

*Advances in Applied Mathematics*,

*38*(2), 258-266. https://doi.org/10.1016/j.aam.2006.05.002