Connected incomparability graph

Question

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points iff they are incomparable.

I am interested in posets for which the incomparability graph is connected and are maximal for this property. That is, making any pair of incomparable elements comparable disconnects the incomparability graph.

Is there any hope of classifying such partial orders? For example, the set $\{a_1, \ldots, a_{n-1},b\}$ with $a_i < a_j$ when $i < j$ and $b$ incomparable to each $a_i$ is maximal in the desired sense. (If we make $b$ comparable to some $a_i$ then this $a_i$ will be comparable to everything and hence an isolated point.) But there are other examples that don't look like this.

Answer 1

Proposition: Such posets have exactly two maximal elements, one of which lies above every non-maximal element, I call this one supermaximal (according with the original definition of Jeremy Rickard in the first link). Also, removing the supermaximal element leaves the incomparability graph connected (this is easy to see, it has degree 1). So these posets are precisely the bichains as defined in multiple ways by Matthew Fayers (2nd link). One of the definitions is the solution Jan Kynčl was proposing: The posets whose incomparability graph is a caterpillar.

Lemma: If the incomparability graph of a poset $P$ is disconnected, we can partition $P$ into two parts $X<Y$, that is $x<y\;\forall x\in X, y\in Y$.

Proof: Let $M$ be a connected component of the incomparability graph and $N=P\setminus M$. Now we distinguish two cases: If $\forall y\in N: (\forall x \in M: x<y)\vee(\forall x \in M: x>y)$, then this gives a natural partition of $N$ into elements bigger and smaller than $M$. By transitivity, the set $X$ of smaller elements does the job. If, $\exists y\in N: (\exists m\in M: m<y)\wedge (\exists x \in M: x>y)$, then there is a natural decomposition of $M$ into the part smaller and the part bigger than $y$. Thus $M$ is disconnected, which is a contradiction.

Proof of Proposition: If the poset had only one maximal element, this would be the greatest element of the poset and thus be disconnected from the rest of the incomparability graph.

Claim: If such a poset $P$ has at least three maximal elements $x,y,z$, then we can add one of the cover relation between any two of them, say $z>y$ or $y>z$.

Proof of Claim: Take the transitive closure of $z>y$. This adds only relations of the form $e\le z$ for some elements $e\in P$. Assume this disconnects the incomparability graph, and let $X_z, Y_z$ be the partition classes given by the lemma. Since the incomparability graph was connected before, there is $x_z\in X_z$ (originally) incomparable to $z$ in $P$. Now play the same game adding the relation $y>z$ and you get $x_y\in X_y$ incomparable to $y$ in $P$. This means $x_y\in Y_z$, because $z\in Y_z$ and $(z,x),(x,y),(y,x_y)$ are incomparable pairs. Yet this would imply $x_y>x_z$ which is a contradiction by the symmetry of the construction. Thus the poset has exactly two maximal elements $x,y$.

Now assume none of $x,y$ is supermaximal: Then there are $p,q\in P$ incomparable to $x,y$ respectively. They are both non-maximal so $p<y,q<x$. Now add the cover-relation $x>p$ and take the transitive closure. Again, this adds only relations of the form $e<x$. We get an element $x_x\in X_x$ incomparable to $x$ in $P$ in a similar way as above. Now $q\in Y_x$, since $x\in Y_x$ and $(x,y),(y,q)$ are still incomparable. But this means already $x>q>x_x$ in the original poset. Thus we reach a contradiction.

As Nik pointed out, while it is quite obvious, that the obtained poset has a connected incomparability graph, it is not obvious that it is maximal in that regard. Imagine it is not. Let $P$ be the original poset with maximal elements $x,y$, $P_x$ its truncation by deleting the supermaximal element $x$ and $P_x^>$ its extension.

Case 1: $y$ is maximal in $P_x^>$: Then we can add (back) an element $x$ to $P_x^>$ that is greater than all elements except $y$, yielding a poset $P^>$, that is connected and has all relations that $P$ had. Also, the number of relations it has is strictly greater than the number of relations of $P$, since the difference of number of relations of $P$ and $P_x$ as well as $P_x^>$ and $P^>$ is precisely $|P|-2$, the number of relations of $x$. So $P$ was not maximal, which is a contradiction.

Case 2: Since the poset $P_x^>$ is still connected, it has at least two maximal elements $a,b$, these are maximal in $P_x$ as well. In the claim above we convinced ourselves, that since $P_x$ has at least three maximal elements, we can add a cover relation between $a$ and $b$ without disconnecting the comparability graph. Now we could also have chosen this extension to be $P_x^>$ and ended up in the first case, so this is a contradiction as well.

My proof shows in particular that minimal connected incomparability graphs are minimal connected graphs, aka trees, by iteratively pointing at a leaf of the graph, which one can delete.

Related links:

Has anyone seen these posets before?

http://www.maths.qmul.ac.uk/~mf/papers/posets.pdf

Answer 2

It is possible to classify the trees that are incomparability graphs (also called co-comparability graphs) as caterpillars.

Minimal connected graph is a tree, and a co-comparability graph does not contain a subdivided $K_{1,3}$ as an induced subgraph; it is denoted by $T_2$ on http://www.graphclasses.org/classes/gc_147.html.

Trees with no induced $T_2$ are caterpillars (https://en.wikipedia.org/wiki/Caterpillar_tree), and it is easy to see that every caterpillar can be represented as an intersection graph of $x$-monotone curves between two vertical lines; in fact, it is a permutation graph (and therefore co-comparability graph).

The next step would be to show that minimal connected incomparability graphs are trees. It might be helpful to use the representation of incomparability graphs as intersection graphs of x-monotone curves between two vertical lines; this can also help with characterizing the posets, since the order in the poset corresponds to vertical orderning of disjoint curves in the representation.