Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

DOI10.1017/S0963548317000013zbMATH Open1371.05301arXiv1408.4093OpenAlexW2964123780MaRDI QIDQ5366963FDOQ5366963

Authors: Abhishek Methuku, Dömötör Pálvölgyi 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We prove that for every poset $P$, there is a constant $C$ such that the size of any family of subsets of $[n]$ that does not contain $P$ 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.

Full work available at URL: https://arxiv.org/abs/1408.4093

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

zbMATH Keywords

Marcus-Tardos theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

Cites Work

• An inequality related to the isoperimetric inequality
• Davenport-Schinzel theory of matrices
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Excluded permutation matrices and the Stanley-Wilf conjecture
• A simple proof of the Erdős-Chao Ko-Rado theorem
• On a lemma of Littlewood and Offord
• Set families with a forbidden subposet
• Title not available (Why is that?)
• Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
• On families of subsets with a forbidden subposet
• Diamond-free families
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• On 0-1 matrices and small excluded submatrices
• A note on the largest size of families of sets with a forbidden poset
• Set families with a forbidden induced subposet
• Set families with forbidden subposets
• The method of double chains for largest families with excluded subposets
• Induced and non-induced forbidden subposet problems
• An improvement of the general bound on the largest family of subsets avoiding a subposet
• An upper bound on the size of diamond-free families of sets
• Extremal functions of forbidden multidimensional matrices

Cited In (23)

• Title not available (Why is that?)
• Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
• Almost all permutation matrices have bounded saturation functions
• Forbidding rank-preserving copies of a poset
• Forbidden induced subposets of given height
• Packing the Boolean lattice with copies of a poset
• On an extremal problem for poset dimension
• 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
• Boolean lattices: Ramsey properties and embeddings
• Set families with forbidden subposets
• Supersaturation and stability for forbidden subposet problems.
• 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
• Title not available (Why is that?)
• 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)