Can I read Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems on EtoBox?

Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems by Methuku, Abhishek; Pálvölgyi, Dömötör is a scholarly article available to read on EtoBox.

What is Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems about?

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{\binom{n}{\lfloor\frac{n}{2}\rfloor}}$, 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.

Author

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

Published

2014

Language

EN