Originator(s): Tom Trotter (Georgia Tech)
Definitions: A removable pair of elements in a partially ordered set P is a pair {x,y} such that removing x and y does not drop the dimension of the poset by more than one.
Conjecture: Every poset with at least three elements has a removable pair.
Background/motivation: For n >= 4, every poset with n elements has dimension at most n/2, as proved by Hiraguchi [H2] and later more simply by Kimble [K] and independently by Trotter [Tr1]. The Removable Pair Conjecture would imply this directly.
Comments/Partial results: A number of results obtain removable pairs when special conditions are satisfied. A minimal element and maximal element that are incomparable form a removable pair. If x and y are maximal elements with the set of elements below x contained in the set of elements below y, then {x,y} is a removable pair. If x<y, and there are at most dimP-3 ordered incomparable pairs (a,b) such that x<a and b<y, then {x,y} is a removable pair (Hiraguchi [H1]). If x and y are incomparable, and there are at most dimP-3 ordered incomparable pairs (a,b) such that a is comparable to both x and y and b is incomparable to both x and y, then {x,y} is a removable pair (Kelly-Trotter [KT1]).
Tator [Ta] gave a short proof that for n≥4 there always exist four points whose removal decreases the dimension by at most 2.
An unforced pair is an ordered incomparable pair (x,y) such that x<y cannot be forced by adding any other comparability to the poset. A set of linear extensions of P has intersection P if and only for every unforced pair (x,y), the relation x<y appears in at least one of the extensions. (In the literature, a critical pair is a pair (y,x) such that (x,y) is an unforced pair, and the criterion for realizing P is described as reversing all the critical pairs.)
Trotter and Bogart [TB1] posed a stronger conjecture that every unforced pair is a removable pair, but Reuter [R] found a counterexample in dimension 4. Kierstead and Trotter [KT2] produced counterexamples for all dimensions at least 5. The examples of [R] and [KT2] appear here. Trotter and Bogart [TB2] showed that the stronger conjecture holds for interval dimension.
Further discussion of the problem appears in Trotter [Tr2, Tr3], where the diagram of Reuter's example should be corrected as given above.
References:
[H1] Hiraguchi, T. On the dimension of partially ordered sets.
Sci. Rep. Kanazawa Univ. 1, (1951). 77--94.
[H2] Hiraguchi, T. On the dimension of orders.
Sci. Rep. Kanazawa Univ. 4, (1955). 1--20.
[KT1] Kelly, D.; Trotter, W. T. Dimension theory for ordered sets.
Ordered sets (Banff, Alta., 1981), pp. 171--211,
NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., 83,
Reidel, Dordrecht-Boston, Mass., 1982.
[KT2] Kierstead, H. A.; Trotter, W. T. A note on removable pairs.
Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988),
739--742, Wiley-Intersci. Publ., Wiley, New York, 1991.
[K] Kimble, R. J. Extremal Problems in Dimension Theory for Partially Ordered
Sets. Ph.D. Thesis, Massachusetts Institute of Technology, 1973.
[R] Reuter, K. Removing critical pairs. Order 6 (1989), no. 2, 107--118.
[Ta] Tator, C. On the Dimension of Ordered Sets.
Diplom. Thesis, Technische Hochschule Darmstadt.
[Tr1] Trotter, W. T. A forbidden subposet characterization of an
order-dimension inequality. Math. Systems Theory 10 (1976), no. 1, 91--96.
[Tr2] Trotter, W. T. Combinatorics and partially ordered sets: Dimension
theory. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins
University Press, Baltimore, MD, 1992. xvi+307 pp.
[Tr3] Trotter, W. T. Progress and new directions in dimension theory for finite
partially ordered sets. Extremal problems for finite sets (Visegra'd, 1991),
457--477, Bolyai Soc. Math. Stud., 3, Ja'nos Bolyai Math. Soc., Budapest, 1994.
[TB1] Trotter, W. T.; Bogart, K. P. Maximal dimensional partially ordered sets.
III. A characterization of Hiraguchi's inequality for interval dimension.
Discrete Math. 15 (1976), no. 4, 389--400.
[TB2] T., W. T., Jr.; Bogart, K. P. On the complexity of posets.
Discrete Math. 16 (1976), no. 1, 71--82.