Regressions and monotone chains: A ramsey-type extremal problem for partial orders |
| |
| Authors: | D. B. West W. T. Trotter Jr. G. W. Peck P. Shor |
| |
| Affiliation: | (1) Department of Mathematics, University of Illinois, 61801 Urbana, Illinois, USA;(2) University of South Carolina, 29208 Columbia, South Carolina, USA;(3) Massachusetts Institute of Technology, 02139 Cambridge, Massachusetts, USA |
| |
| Abstract: | Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx 1<x 2 <...<x k such thatg(x 1)≦g(x 2)≦...≦g(x k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451. |
| |
| Keywords: | 05 C 55 06 A 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
