Is the crown the only DAG whose partial order dimension can be greater than 2?

231 Views Asked by At

Is the crown graph the only type of directed acyclic graph whose partial order dimension could be potentially greater than 2 (given sufficiently many vertices in sets $U$ and $V$), given that for all edges, each points from a vertex in set $U$ to a vertex in set $V$?

Are there any DAGs (other than crowns) that have a partial order dimension greater than 2?

1

There are 1 best solutions below

0
On BEST ANSWER

No, there are many other directed acyclic graphs with dimension greater than $2$.

By Schnyder's Theorem (1989), a graph is planar if and only if its incidence poset has dimension $\le 3$. The incidence poset is always a height $2$ directed acyclic graph. Therefore, all incidence posets of non-planar graphs have dimension $>3$.

Consider the non-planar graph $K_5$. It's incidence poset has $\binom{5}{2}$ maximal elements and $5$ minimal elements (so it's not a crown). By Schnyder, since $K_5$ is non-planar it's incidence poset must have dimension at least $4$.