MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Is there an upper bound on the number of uppersets/antichains in a partially ordered set

For my thesis I've been doing a lot of research concerning upwards closed sets and anti chains. A while ago while searching I thought I stumbled across a proof that gave an upper bound on the number of anti-chains/uppersets in a partially ordered set.

Now I'm not 100% sure someone has proven a fair upper bound (ofc n^2 is always true) and after hours of searching I can't seem to find it (anymore). I did come across some papers concerning upper bounds on special types antichains or upper bounds in special cases of partially ordered sets but I'm afraid they weren't near any level that I could comprehend.

-

If the poset is a power set, then the answer is $2^{{n \choose n/2}(1-o(1))}$.

A brief history of the problem:

http://mathworld.wolfram.com/DedekindsProblem.html

http://oeis.org/A014466

http://www.ams.org/journals/proc/1969-021-03/S0002-9939-1969-0241334-6/S0002-9939-1969-0241334-6.pdf

-
And if the poset is totally unordered, e.g. an antichain, then it is roughly 2 to the power of the number of elements in the antichain. Gerhard "Ask Me About System Design" Paseman, 2012.04.15 – Gerhard Paseman Apr 15 2012 at 16:48
@domotorp: what is the 'o' function in (1-o(1))? Thanks for all the links btw, gives me some great material to delve through tomorrow. @GerhardPaseman: doh, of course you're right, there are plenty (infinite) partially ordered sets that have N^2 antichains didn't think of that :/. – royalexander Apr 15 2012 at 21:21
@royalalexander: o(1) denotes a quantity that goes to zero as $n$ goes to infinity. You may check en.wikipedia.org/wiki/…, if you will – Woett Apr 15 2012 at 23:00
Ah I'm familiar with big-Oh, but I didn't know about little-Oh, thanks for the link. – royalexander Apr 16 2012 at 8:00
@Woett, still trying to wrap my head around it. So (1-o(1)) approaches 1 as n goes to infinity, this leaves me with 2^(ncr(n, n/2)) for the upper bound on the number of antichains in P. However this is larger than 2^n, which is number of all possible subsets in P. Or isn't domotorp talking about the binomial coefficient? I think he is from what I can make out of the last paper. Where did I go wrong? – royalexander Apr 16 2012 at 8:36
show 2 more comments