Fibres and ordered set coloring (Q1177956): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Henry A. Kierstead / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jack E. Graver / rank | |||
Normal rank |
Revision as of 00:41, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fibres and ordered set coloring |
scientific article |
Statements
Fibres and ordered set coloring (English)
0 references
26 June 1992
0 references
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\).
0 references
set coloring
0 references
fibre of a partially ordered set
0 references
co-NP-complete
0 references
NP-hard
0 references