Fibres and ordered set coloring (Q1177956): Difference between revisions

Let \(P=(X,\leq)\) be a partially ordered set; a subset \(F\subset X\) is called a fibre of \(P\) if each antichain contains an element from \(F\). We let \(\lambda\) denote the least real number so that, for each partially ordered set \(P=(X,\leq)\) there exists some fibre \(F\) with \(| F|\leq\lambda| X|\). Using a coloring argument the authors prove that \(\lambda\leq 2/3\). Also they show that: Theorem 3. The problem of determining whether a given subset of an ordered set \(P\) is a fibre of \(P\) is co-NP-complete. Theorem 4. It is NP-hard to determine whether, for a given ordered set \(P\) and integer \(k\), \(P\) has a fibre of size \(k\).