Forbidden induced subposets in the grid

2017/05/26 by István Tomon, Tomon, István
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.1705.09551

openalex publication_date 2017/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short paper, we prove the following generalization of a result of Methuku and Pálvölgyi. Let P be a poset, then there exists a constant C_P with the following property. Let k and n be arbitrary positive integers such that n is at least the dimension of P, and let w be the size of the largest antichain of the grid [k]ⁿ endowed with the usual pointwise ordering. If S is a subset of [k]ⁿ not containing an induced copy of P, then |S|≤ C_Pw.

Citations

• Lubell mass and induced partially ordered sets

Related

• Forbidden induced subposets of given height
• Forbidden subposet problems in the grid
• Forbidden hypermatrices imply general bounds on induced forbidden\n subposet problems
• On an extremal problem involving a pair of forbidden posets
• Standard Examples as Subposets of Posets