Regressions and monotone chains II: The poset of integer intervals |
| |
Authors: | Noga Alon W T Trotter Douglas B West |
| |
Institution: | (1) Tel Aviv University, Tel Aviv, Israel;(2) Arizona State University, 85287 Tempe, AZ, U.S.A.;(3) University of Illinois, 61801 Urbana, IL, U.S.A. |
| |
Abstract: | A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x) x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x
1<...ksuch that (x
1) ...![le](/content/q47u237232308n8g/xxlarge8804.gif) (xk). Let P
nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P
nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x
t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + k, k) , where k 0 as k![rarr](/content/q47u237232308n8g/xxlarge8594.gif) . Alternatively, the largest k such that every regression on P
nis guaranteed to have a monotone k-chain lies between lg*(n) and lg*(n)–2, inclusive, where lg*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element. |
| |
Keywords: | 05C55 06A10 62J |
本文献已被 SpringerLink 等数据库收录! |
|