Forbidding rank-preserving copies of a poset

2017/10/25 by Gerbner, Dániel, Methuku, Abhishek, Nagy, Dániel T. +2
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1710.09086

Abstract

The maximum size, La(n,P), of a family of subsets of [n]=\1,2,...,n\ without containing a copy of P as a subposet, has been intensively studied. Let P be a graded poset. We say that a family F of subsets of [n]=\1,2,...,n\ contains a rank-preserving copy of P if it contains a copy of P such that elements of P having the same rank are mapped to sets of same size in F. The largest size of a family of subsets of [n]=\1,2,...,n\ without containing a rank-preserving copy of P as a subposet is denoted by La_rp(n,P). Clearly, La(n,P) ≤ La_rp(n,P) holds. In this paper we prove asymptotically optimal upper bounds on La_rp(n,P) for tree posets of height 2 and monotone tree posets of height 3, strengthening a result of Bukh in these cases. We also obtain the exact value of La_rp(n,\Y_h,s,Y_h,s'\) and La(n,\Y_h,s,Y_h,s'\), where Y_h,s denotes the poset on h+s elements x₁,…,x_h,y₁,…,y_s with x₁

Related

• Generalized forbidden subposet problems
• On the maximum size of B₃-free and D_s-free families
• Largest family without a pair of posets on consecutive levels of the Boolean lattice
• On the number of containments in P-free families
• Rainbow Turán problems for forbidden subposets