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. |
Year | Venue | Field |
---|---|---|
2018 | ELECTRONIC JOURNAL OF COMBINATORICS | Discrete mathematics,Combinatorics,Bijection,Conjecture,Mathematics,Partially ordered set |
DocType | Volume | Issue |
Journal | 25 | 3.0 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dániel Gerbner | 1 | 46 | 21.61 |
Balázs Patkós | 2 | 85 | 21.60 |
Máté Vizer | 3 | 27 | 14.06 |