On the fractional dimension of partially ordered sets (Q1344614): Difference between revisions

Let \({\mathbf P} = (X,P)\) be a poset and let \(F = \{M_ 1, \dots, M_ t\}\) be a set of linear extensions of \({\mathbf P}\). Then \(F\) is called a \(k\)-fold realizer of \({\mathbf P}\) if for each incomparable pair \((x,y)\), there are at least \(k\) linear extensions in \(F\) which reverse the pair \((x,y)\). The fractional dimension of \({\mathbf P}\), denoted by \(\text{fdim} ({\mathbf P})\), is defined as the least real number \(q \geq 1\) for which there exists a \(k\)-fold realizer \(F\) of \({\mathbf P}\) so that \(k/t \geq {1 \over q}\). For a point \(x \in X\) define the degree of \(x\) as the number \(\deg (x)\) of points comparable (but not equal) to \(x\) in \(P\) and set \(\Delta ({\mathbf P}) : = \max \{\deg (x) : x \in X\}\). Theorem 3.2. If \({\mathbf P}\) is not an antichain, then \(\text{fdim} (P) \leq 1 + \Delta ({\mathbf P})\). It is shown that if \({\mathbf P}\) contains an antichain \(A\) such that all antichains disjoint from \(A\) have size at most \(w \geq 4\), then \(\text{fdim} ({\mathbf P}) \leq 2w\), and this bound is asymptotically best possible (Theorem 8.2). Some other results are proved concerning the fractal dimension of posets. Five open problems conclude the paper, e.g., given rational numbers \(p\) and \(q\), what is the minimum value of \(\text{fdim} ({\mathbf P} \times {\mathbf Q})\), where \(\text{fdim} ({\mathbf P})=p\) and \(\text{fdim} ({\mathbf Q}) = q\)?