Extensions of the linear bound in the Füredi-Hajnal conjecture
From MaRDI portal
Publication:2643869
DOI10.1016/J.AAM.2006.05.002zbMATH Open1121.05118arXivmath/0507164OpenAlexW2058473382WikidataQ123094137 ScholiaQ123094137MaRDI QIDQ2643869FDOQ2643869
Authors: Martin Klazar, Adam W. Marcus 
Publication date: 27 August 2007
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Abstract: 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}).
Full work available at URL: https://arxiv.org/abs/math/0507164
Recommendations
- Better upper bounds on the Füredi-Hajnal limits of permutations
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
- scientific article; zbMATH DE number 1504588
Cites Work
- Title not available (Why is that?)
- Davenport-Schinzel theory of matrices
- Analytic combinatorics of non-crossing configurations
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Finite automata and pattern avoidance in words
- Noncrossing partitions
- Noncrossing Partitions in Surprising Locations
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Crossings and nestings of matchings and partitions
- Title not available (Why is that?)
- On partitions avoiding 3-crossings
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- On 0-1 matrices and small excluded submatrices
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- Title not available (Why is that?)
Cited In (36)
- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- Saturation of Multidimensional 0-1 Matrices
- Almost all permutation matrices have bounded saturation functions
- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- Jumps in speeds of hereditary properties in finite relational languages
- Extremal functions of excluded tensor products of permutation matrices
- On grids in topological graphs
- Counting ordered graphs that avoid certain subgraphs
- Forbidden induced subposets of given height
- Quasi-planar Graphs
- On an extremal problem for poset dimension
- Bounds on parameters of minimally nonlinear patterns
- Extremal problems for pairs of triangles
- A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
- Title not available (Why is that?)
- Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
- Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
- Extremal functions of forbidden multidimensional matrices
- A linear bound on the dimension in Green-Ruzsa's theorem
- Forbidden formations in multidimensional 0-1 matrices
- Linear bounds on matrix extremal functions using visibility hypergraphs
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Set partition patterns and the dimension index
- Uniform chain decompositions and applications
- Partitioning ordered hypergraphs
- Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- On disjoint crossing families in geometric graphs
- Sequence saturation
- Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
- Forbidden configurations and product constructions
- Set families with forbidden subposets
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
- Better upper bounds on the Füredi-Hajnal limits of permutations
- Forbidden subposet problems in the grid
- The length of an s-increasing sequence of r-tuples
- An improvement of the general bound on the largest family of subsets avoiding a subposet
This page was built for publication: Extensions of the linear bound in the Füredi-Hajnal conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643869)
