# Is counting maximal cliques in an incomparability graph #P-complete?

This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (i.e., we want to count maximal antichains in a finite poset)? This question seems natural enough that I suspect that it has been considered before, but I have not been able to locate it in the literature.

• Actually, if you look at the proof, you'll see that #P-completeness is proved for a class of posets in which all maximal antichains have the same cardinality. Namely, start with any bipartite graph $G=(V,E)$ with $n$ vertices and construct a bipartite graph $G'$ with $2n$ vertices by adding $n$ new vertices $\{v' : v\in V\}$ and $n$ new edges $\{(v,v'): v\in V\}$. Then, if $V_1$ and $V_2$ is a bipartition of the vertex set of $G'$, define a poset on $V_1\cup V_2$ by setting $x<y$ if $x\in V_1$ and $y\in V_2$ and $x$ and $y$ are adjacent in $G'$. So this does answer my question. Aug 7 '11 at 2:46