Forbidden subposet problems for traces of set families

Gerbner, Dániel and Patkós, Balázs and Vizer, Máté (2018) Forbidden subposet problems for traces of set families. ELECTRONIC JOURNAL OF COMBINATORICS, 25 (3). pp. 1-19. ISSN 1097-1440

Preview

Text 1706.01212v1.pdf Download (228kB) | Preview

Abstract

In this paper we introduce a problem that bridges forbidden subposet and forbidden subconfiguration problems. The sets F-1, F-2 , . . . , F-vertical bar p vertical bar form a copy of a poset P, if there exists a bijection i : P -> {F-1, F-2 , . . , F-vertical bar p vertical bar} such that for any p, p'is an element of P the relation p < p p' implies i(p) not subset of i(p'). A family F of sets is P -free if it does not contain any copy of P. The trace of a family F on a sets X is F vertical bar( X) := { F boolean AND X : F is an element of F}. We introduce the following notions: F subset of 2([n]) is l-trace P-free if for any l-subset L subset of [n], the family F vertical bar vertical bar (L) is P-free and F is trace P -free if it is l-trace P-free for all l <= n. As the first instances of these problems we determine the maximum size of trace B-free families, where B is the butterfly poset on four elements a, b, c, d with a, b < c, d and determine the asymptotics of the maximum size of (n - i)-trace K-r,K- (s)-free families for i = 1, 2. We also propose a generalization of the main conjecture of the area of forbidden subposet problems.

Actions (login required)

Edit Item