3
$\begingroup$

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no asteroidal triple in the comparability graph, then can we say that the poset is 2-dimensional? I have worked with quite a few examples, every poset in the irreducible 3-dim posets has at-least one asteroidal triple (some have more than one, like the crown poset). If not a proof it would be fine to even show an example which contradicts the statement.

edit: also a classical result of Lekkerkerker and Boland states that a graph is an interval graph if it is chordal and Asteroidal-triple free. But the dimension of an interval graph is not bound. So can there be a poset whose comparability graph is AT-free but is of dimension 3 or more?

definition of an asteroidal triple: Three independent vertices of a graph form an asteroidal triple if every two of them are connected by a path avoiding the neighborhood of the third one. A graph is asteroidal triple-free (AT-free, for short) if it contains no asteroidal triple.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

It seems that the answer is negative.

A graph $G$ is a co-comparability graph if its complement is a comparability graph. The comparability graphs of posets of dimension 2 are exactly the comparability graphs that are also co-comparability. These graphs are also known as permutation graphs.

Every co-comparability graph is asteroidal triple-free, but the converse in general is not true. Your question is equivalent to asking whether comparability $\cap$ co-comparability = comparability $\cap$ asteroidal triple-free. By inspecting the list of forbidden induced subgraphs of co-comparability graphs and comparing to the ones of asteroidal triple-free graphs and comparability graphs, the answer seems to be negative: graphs of the family co-XF$_1^{2n+3}$, which are forbidden for co-comparability graphs seem to belong to comparability $\cap$ asteroidal triple-free.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .