13
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ The following example with three maximal elements shows that one has to be more careful about which cover relation to add: $P=\{a,b,c,d\}$, with $a,b,c$ maximal, and the only comparable pairs are $d<b$ and $d<c$. Then adding the relation $a>b$ disconnects the incomparability graph. $\endgroup$ – Jan Kyncl Jul 18 at 1:01
  • $\begingroup$ @JanKyncl: can the proof be fixed? $\endgroup$ – Nik Weaver Jul 18 at 3:25
  • $\begingroup$ @JanKyncl Thank you for pointing out a gap in my proof. I am a big fan of your work by the way. I think it should be fixed now, but feel free to ask if there is something else not (well) explained. $\endgroup$ – Felix Schröder Jul 18 at 14:04
  • 1
    $\begingroup$ The proof now looks correct, very nice. The final comment needs proof though --- you have to show that after deleting the leaf what's left is still minimal. $\endgroup$ – Nik Weaver Jul 18 at 19:37
  • $\begingroup$ @NikWeaver Imagine it is not. Let $P$ be the original poset $P'$ its truncation by deleting the supermaximal element and $P^*$ its extension. The only cover relations we can add are such that the non-deleted maximal element in $P$ is not maximal anymore, because otherwise we could just add the supermaximal element back in. Since the poset $P^*$ is still connected, it has at least two maximal elements, these are maximal in $P'$ as well. By my arguments, you can add either cover relations between the two. Contradiction, as we can add the supermaximal element back in. More formal edit will follow $\endgroup$ – Felix Schröder Jul 19 at 16:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ From your link it looks like any subgraph of a co-comparability graph is also a co-comparability graph. Is that right? (Otherwise I wonder if a minimal connected co-comparability graph must be a minimal connected graph.) $\endgroup$ – Nik Weaver Dec 11 '18 at 14:58
  • $\begingroup$ Your answer is very helpful --- thank you --- but it doesn't directly solve my problem since I wanted to know what are the maximal posets. It isn't even clear to me that given a maximal poset with connected co-comparability graph, that graph has to be a minimal connected co-comparability graph ... $\endgroup$ – Nik Weaver Dec 11 '18 at 14:59
  • $\begingroup$ @Nik Weaver A subgraph of a co-comparability graph does not have to be a co-comparability graph: for example, all complete graphs are co-comparability graphs, but not all graphs are co-comparability graphs. But you are right that it is missing to show that minimal connected co-comparability graphs are indeed trees. $\endgroup$ – Jan Kyncl Dec 11 '18 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.