Largest induced suborders satisfying the chain condition |
| |
Authors: | Nathan Linial Michael Saks Peter Shor |
| |
Institution: | (1) Department of Computer Science, Hebrew University, Jerusalem, Israel;(2) Bell Communications Research, 435 South St., 07960 Morristown, NJ, USA;(3) Department of Mathematics, MIT, 02139 Cambridge, MA, USA |
| |
Abstract: | For a finite ordered set P, let c(P) denote the cardinality of the largest subset Q such that the induced suborder on Q satisfies the Jordan-Dedekind chain condition (JDCC), i.e., every maximal chain in Q has the same cardinality. For positive integers n, let f(n) be the minimum of c(P) over all ordered sets P of cardinality n. We prove:
|
| |
Keywords: | 06A05 |
本文献已被 SpringerLink 等数据库收录! |
|