×

On some minimal problem. (English) Zbl 0554.06003

It is known [N. Megiddo, Bull. Am. Math. Soc. 82, 274-276 (1976; Zbl 0361.06001)] that not any cyclic order has a linear extension. The paper deals with the problem of a minimal integer n such that there exists a cyclic order on an n-element set which has no linear extension; by N. Megiddo, \(n\leq 13\). The paper contains an example improving this estimation for \(n\leq 10\).
Reviewer: I.Chajda

MSC:

06A06 Partial orders, general
05A20 Combinatorial inequalities

Citations:

Zbl 0361.06001
PDFBibTeX XMLCite
Full Text: EuDML