Welcome to MathOverflow

Question

1

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

flag	asked Aug 3 2011 at 13:08 Peng Zhang 33●3

2

So, what is the given structure of the poset? The answer will depend heavily on it. – Emil Jeřábek Aug 3 2011 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 2011 at 15:04

hi Emil, what if it is just a poset? – klaraspina Aug 3 2011 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 2011 at 15:23

5

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 2011 at 15:52

show 2 more comments

Timothy Chow · Accepted Answer · 2011-08-03 20:53:28Z UTC

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.

What is the number of maximal antichain in a poset?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.