Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
From MaRDI portal
Publication:5366963
Abstract: We prove that for every poset , there is a constant such that the size of any family of subsets of that does not contain as an induced subposet is at most , settling a conjecture of Katona, and Lu and Milans. We obtain this bound by establishing a connection to the theory of forbidden submatrices and then applying a higher dimensional variant of the Marcus-Tardos theorem, proved by Klazar and Marcus. We also give a new proof of their result.
Recommendations
- Forbidden submatrices: some new bounds and constructions
- Induced and non-induced forbidden subposet problems
- scientific article; zbMATH DE number 1463403
- Generalized forbidden subposet problems
- On forbidden submatrices
- On linear forbidden submatrices
- Forbidden subposet problems for traces of set families
- Supersaturation and stability for forbidden subposet problems.
- Saturation problems about forbidden 0-1 submatrices
- Forbidden submatrices
Cites work
- scientific article; zbMATH DE number 3845613 (Why is no real title available?)
- A note on the largest size of families of sets with a forbidden poset
- A simple proof of the Erdős-Chao Ko-Rado theorem
- An improvement of the general bound on the largest family of subsets avoiding a subposet
- An inequality related to the isoperimetric inequality
- An upper bound on the size of diamond-free families of sets
- Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
- Davenport-Schinzel theory of matrices
- Diamond-free families
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Extremal functions of forbidden multidimensional matrices
- Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
- Induced and non-induced forbidden subposet problems
- On 0-1 matrices and small excluded submatrices
- On a lemma of Littlewood and Offord
- On families of subsets with a forbidden subposet
- Set families with a forbidden induced subposet
- Set families with a forbidden subposet
- Set families with forbidden subposets
- The method of double chains for largest families with excluded subposets
Cited in
(23)- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- scientific article; zbMATH DE number 4125409 (Why is no real title available?)
- Almost all permutation matrices have bounded saturation functions
- Forbidding rank-preserving copies of a poset
- Forbidden induced subposets of given height
- On an extremal problem for poset dimension
- Packing the Boolean lattice with copies of a poset
- Set families with a forbidden induced subposet
- Induced and non-induced forbidden subposet problems
- Induced and non-induced poset saturation problems
- On forbidden submatrices
- Poset Ramsey number \(R(P,Q_n)\). II: \(\mathrm{N}\)-shaped poset
- Uniform chain decompositions and applications
- Poset Ramsey numbers: large Boolean lattice versus a fixed poset
- Set families with forbidden subposets
- Supersaturation and stability for forbidden subposet problems.
- Boolean lattices: Ramsey properties and embeddings
- A LYM inequality for induced posets
- Forbidden subposet problems in the grid
- A simple proof for a forbidden subposet problem
- Forbidden subposet problems with size restrictions
- scientific article; zbMATH DE number 1463403 (Why is no real title available?)
- An improvement of the general bound on the largest family of subsets avoiding a subposet
This page was built for publication: Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366963)
