This is a topic I am recently working on. Given a poset, how many different antichains are there?
I find little literature on it. And I am interested whether there is a closed formula, or a tight lowerbound or upperbound given the structure of the poset, or approximation ratio guaranteed algorithm. 


There is a post concerning "number of antichain in poset" here[link text](https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset). 


Thank you very much in advance. :-)



What is the number of maximal antichain in a poset?
I'm going to assume that you're counting *maximal* antichains because the word "maximal" occurs in the title, even though it doesn't appear in the main text of your question.


You will probably find more literature if you phrase your problem as counting maximal cliques in an incomparability graph. For a general graph, Valiant showed that counting the number of maximal cliques is #P-complete (*SIAM J. Computing* **8** (1979), 410–421). I am not sure whether the problem remains #P-complete when restricted to incomparability graphs. Incomparability graphs are perfect, so at least it's possible to determine the size of the largest clique in polynomial time, but that doesn't immediately imply anything about the complexity of the counting problem. You could try asking your question on [cstheory.stackexchange.com](http://cstheory.stackexchange.com).


There are algorithms that enumerate maximal cliques in time polynomial in the number of maximal cliques, so if the total number of maximal cliques is polynomial then you can count them in polynomial time. See for example the [paper by Rosgen and Stewart](http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/707/1817). In general, though, incomparability graphs could have exponentially many maximal cliques.


**EDIT:** I still don't know whether your problem is #P-complete, but I'm beginning to suspect that it is. If so, perhaps the techniques in Salil Vadhan's paper "The complexity of counting in sparse, regular, and planar graphs" (*SIAM J. Comput.* **31** (2001), 398–427) will be useful for proving it. 


