2014/08/18 by Abhishek Methuku, Methuku, Abhishek, Dömötör Pálvölgyi +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1408.4093
openalex publication_date 2014/08/18 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We prove that for every poset P, there is a constant C such that the size\nof any family of subsets of [n] that does not contain P as an induced\nsubposet is at most C binomn lfloor\(n)/(2) rfloor, settling a\nconjecture of Katona, and Lu and Milans. We obtain this bound by establishing a\nconnection to the theory of forbidden submatrices and then applying a higher\ndimensional variant of the Marcus-Tardos theorem, proved by Klazar and Marcus.\nWe also give a new proof of their result.\n