12
$\begingroup$

An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, it is known that it is #P-hard, given a poset, to compute its number of antichains.

My question is whether this hardness result is known to extend to restricted classes of posets. More specifically, I am interested in posets which are distributive lattices. Is it #P-hard to count antichains in distributive lattices?

Of course, one could also ask for which classes of posets is hardness, or tractability, known to hold. Has there been any work on this since Provan and Ball?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Interesting question. My intuition is that the answer should be no, because most distributive lattices can be compressed down to logarithmic size by using Birkhoff's representation theorem to turn them into a poset (the poset of join-irreducible elements of the lattice), and the ones that this doesn't make much smaller should be too special to be hard. So effectively this is a sparse problem and considerations like Mahaney's theorem should come into play. But that's far from being a proof, which is why I'm leaving it as a comment not as an answer. $\endgroup$
    – David Eppstein
    Commented Nov 12, 2015 at 6:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.