Fractional dimension of partial orders |
| |
Authors: | Graham R. Brightwell Edward R. Scheinerman |
| |
Affiliation: | (1) Department of Statistical and Mathematical Sciences, London School of Economics and Political Science, Houghton Street, WC2A 2AE London, U.K.;(2) Department of Mathematical Sciences, The Johns Hopkins University, 21218-2689 Baltimore, MD, USA |
| |
Abstract: | Given a partially ordered setP=(X, ), a collection of linear extensions {L1,L2,...,Lr} is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someLi (andy<x in someLj). For a positive integerk, we call a multiset {L1,L2,...,Lt} ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theLi's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research. |
| |
Keywords: | 06A06 |
本文献已被 SpringerLink 等数据库收录! |
|