Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

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\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$, 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.

Cited by in corpus (1)

• An improvement of the general bound on the largest family of subsets avoiding a subposet