On the fractional dimension of partially ordered sets
type: Item
instance of: scholarly article
title: On the fractional dimension of partially ordered sets
zbMATH Open document ID: 0820.06001
DOI: 10.1016/0012-365X(94)00109-V
author: Stefan Felsner
author: William T. Trotter
published in: Discrete Mathematics
publication date: 1995-09-11T00:00:00Z
review text: 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\)?
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 722487
zbMATH Keywords: \(k\)-fold realizer
zbMATH Keywords: fractional dimension
zbMATH Keywords: degree
reviewed by: V. N. Saliĭ
MaRDI profile type: Publication
cites work: Maximal dimensional partially ordered sets. II: Characterization of 2n- element posets with dimension n
cites work: Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension
cites work: Fractional dimension of partial orders
cites work: Q5782525
cites work: On the poset of all posets on \(n\) elements
cites work: A decomposition theorem for partially ordered sets
cites work: Posets with large dimension and relatively few critical pairs
cites work: On the dimensions of ordered sets of bounded degree
cites work: Q5598258
cites work: The rank of a distributive lattice
cites work: Inequalities in Dimension Theory for Posets
cites work: A forbidden subposet characterization of an order — dimension inequality
cites work: Q4004146
description: scientific article; zbMATH DE number 722487