**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 dim*P-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 dim*P-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.