Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

Type: 
Lecture
Audience: 
Open to the Public
Thursday, September 25, 2014 - 12:00pm
Add to Calendar
Date: 
Thursday, September 25, 2014 - 12:00pm to 2:00pm
Joint work with Dömötör Pálvölgyi.
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 C (n \choose n/2) , 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. We also present some conjectures.