Abstract | ||
---|---|---|
A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximal antichain of P . Let λ be the smallest constant such that each finite partially ordered set P contains a fibre of size at most λ |P|. We show that λ \ ̌ 2 3 by finding a good 3-coloring of the nontrivial antichains of P . Some decision problems involving fibres are also considered. For instance, it is shown that the problem of deciding if a partially ordered set has a fibre of size at most κ is NP-hard. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1016/0097-3165(91)90083-S | J. Comb. Theory, Ser. A |
Field | DocType | Volume |
Discrete mathematics,Ordered set,Combinatorics,Decision problem,Antichain,Total order,Partially ordered set,Mathematics | Journal | 58 |
Issue | ISSN | Citations |
1 | Journal of Combinatorial Theory, Series A | 19 |
PageRank | References | Authors |
2.74 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dwight Duffus | 1 | 111 | 36.63 |
H. A. Kierstead | 2 | 700 | 78.87 |
W. T. Trotter | 3 | 309 | 110.36 |