Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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" herelink text.

Thank you very much in advance. :-)

share|improve this question
2  
So, what is the given structure of the poset? The answer will depend heavily on it. –  Emil Jeřábek Aug 3 '11 at 14:28
    
at that link you can find how to compute an upperbound. Moreover, if m is the size of the maximal antichain, then 2^m is a lower bound (and of course it can be refined, but I don't know how much...) But if you get more interesting answers, I'm still interested in this question! –  klaraspina Aug 3 '11 at 15:04
    
hi Emil, what if it is just a poset? –  klaraspina Aug 3 '11 at 15:05
4  
What I meant that more information about properties of the poset is needed to get a sensible answer. Otherwise, the number of maximal antichains may be on the one hand as small as $1$ (for a discrete poset) and on the other hand almost exponential in the size of the poset (for a Boolean algebra). –  Emil Jeřábek Aug 3 '11 at 15:23
6  
I have never understood what people mean when they say "closed formula" in this kind of generality. Closed formula in terms of what? –  Qiaochu Yuan Aug 3 '11 at 15:52
show 2 more comments

1 Answer

up vote 6 down vote accepted

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.

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. 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.

share|improve this answer
2  
Counting antichains in a partial order is #P-complete according to the abstract for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected", SIAM J. Comput. 12 (1983), 777-788 (epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/…). –  mhum Aug 6 '11 at 0:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.