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
- 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?)
- 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
- Noncrossing Partitions in Surprising Locations
- Noncrossing partitions
- On 0-1 matrices and small excluded submatrices
- On partitions avoiding 3-crossings
Cited in
(36)- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- Almost all permutation matrices have bounded saturation functions
- Saturation of Multidimensional 0-1 Matrices
- 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
- Counting ordered graphs that avoid certain subgraphs
- On grids in topological graphs
- 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
- Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
- scientific article; zbMATH DE number 7673608 (Why is no real title available?)
- Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
- A linear bound on the dimension in Green-Ruzsa's theorem
- Extremal functions of forbidden multidimensional matrices
- Forbidden formations in multidimensional 0-1 matrices
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- Linear bounds on matrix extremal functions using visibility hypergraphs
- Set partition patterns and the dimension index
- Uniform chain decompositions and applications
- Partitioning ordered hypergraphs
- On disjoint crossing families in geometric graphs
- Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- Sequence saturation
- Forbidden configurations and product constructions
- Set families with forbidden subposets
- Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
- 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)
