Originator: William T. Trotter (presented by Csaba Biro - REGS 2010)
Definitions: A k-fold realizer of a poset is a multiset of its linear extensions in which every ordered pair of incomparable elements occurs (in that order) at least k times. Let t(k) be the size of the smallest k-fold realizer. The dimension of a poset P, written dim(P), is t(1). The fractional dimension of P, written dim*(P), is the infimum over k of t(k)/k. The standard example, written Sn, is the subposet of the subset lattice on {1,...,n} consisting of the sets of size 1 and n-1; it has dimension n.
Background: Fractional dimension relates to dimension in much the same way as fractional chromatic number of graphs relates to chromatic number. Indeed, the dimension is the solution to an integer programming problem, and the fractional dimension is the solution to its linear programming relaxation. From the definition, dim*(P)≤ dim(P). They can be equal (dim(Sn)=dim*(Sn)=n), but they can differ by arbitrarily much. Always dim*(P) is rational, and the achievable values are 1 and all rational numbers at least 2. Always there is a multirealizer that achieves the fractional dimension, so the "infimum" in the definition becomes a "minimum". We study how these parameters change when elements are deleted.
Conjecture 1 (Removable Pair Conjecture; Trotter, 1973): Every finite poset of size at least 3 has two elements whose removal decreases the dimension by at most 1. Such a pair is called a removable pair.
Comments: A basic result in the theory is that the dimension of a poset is bounded by its width (the maximum size of an antichain), and from this Hiraguchi's Inequality dimP≤⌈|P|/2⌉ is not too hard (see [Tr]); Conjecture 1 would imply this immediately. Tator [Ta] proved that a poset of size at least 4 has four elements whose removal decreases the dimension by at most 2. Many sufficient conditions are known that guarantee the existence of a removable pair, but progress on the conjecture has slowed to standstill in recent years.
Conjecture 2 (Trotter): There is a positive constant ε such that every finite poset of size at least 3 has two elements whose removal decreases the fractional dimension by at most 2-ε.
Comments: An elementary result in the theory is that dim(P-x)≥dim(P)-1 whenever x is an element of P. An analogous result is that dim*(P-x)>dim*(P)-1 (unless P is a standard example). Thus removing two elements reduces the fractional dimension by less than 2, but it is not known whether the amount can be bounded away from 2. The standard examples are central to the next conjecture.
Conjecture 3 (Biro): For a fixed real number t greater than 1, there is a positive constant c such that if a poset has 2n points and has dimension at least tn, then it contains a standard example of dimension cn.
Comments: For further reading, see [Tr] concerning dimension and [BS] concerning fractional dimension. For another result on fractional dimension, see [FT].
References:
[BS] Graham R. Brightwell and Edward R. Scheinerman, Fractional
dimension of partial orders, Order 9, (1992), 139-158.
[FT] Stefan Felsner and William T. Trotter, On the fractional
dimension of partially ordered sets, Discrete Math. 136,
(1994), 101-117 (Trends in discrete mathematics).
[Ta] Tator, C. On the Dimension of Ordered Sets.
Diplom. Thesis, Technische Hochschule Darmstadt.
[Tr] William T. Trotter,Combinatorics and partially ordered
sets, The Johns Hopkins University Press, 1992.