Extensions of the linear bound in the Füredi-Hajnal conjecture
From MaRDI portal
Publication:2643869
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}).
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
- Analytic combinatorics of non-crossing configurations
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Crossings and nestings of matchings and partitions
- Davenport-Schinzel theory of matrices
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- Finite automata and pattern avoidance in words
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
- scientific article; zbMATH DE number 1808181 (Why is no real title available?)
- scientific article; zbMATH DE number 1341926 (Why is no real title available?)
- scientific article; zbMATH DE number 2107707 (Why is no real title available?)
- Noncrossing partitions
- Noncrossing Partitions in Surprising Locations
- On 0-1 matrices and small excluded submatrices
- On partitions avoiding 3-crossings
Cited in
(37)- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Forbidden induced subposets of given height
- Bounds on parameters of minimally nonlinear patterns
- On an extremal problem for poset dimension
- A linear bound on the dimension in Green-Ruzsa's theorem
- Partitioning ordered hypergraphs
- Forbidden subposet problems in the grid
- Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
- Extremal problems for pairs of triangles
- On grids in topological graphs
- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- Extremal functions of forbidden multidimensional matrices
- Forbidden formations in multidimensional 0-1 matrices
- Linear bounds on matrix extremal functions using visibility hypergraphs
- Jumps in speeds of hereditary properties in finite relational languages
- Counting ordered graphs that avoid certain subgraphs
- On disjoint crossing families in geometric graphs
- Extremal functions of excluded tensor products of permutation matrices
- Better upper bounds on the Füredi-Hajnal limits of permutations
- Forbidden configurations and product constructions
- Set families with forbidden subposets
- A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
- Quasi-planar Graphs
- An improvement of the general bound on the largest family of subsets avoiding a subposet
- Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
- Set partition patterns and the dimension index
- The length of an s-increasing sequence of r-tuples
- scientific article; zbMATH DE number 7673608 (Why is no real title available?)
- Saturation of Multidimensional 0-1 Matrices
- Uniform chain decompositions and applications
- Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
- Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- Sequence saturation
- A polynomial-time approximation algorithm for complete interval minors
- Almost all permutation matrices have bounded saturation functions
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
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)
