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

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
1  
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 '12 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 :/. –  Roy T. Apr 15 '12 at 21:21
2  
@royalalexander: o(1) denotes a quantity that goes to zero as $n$ goes to infinity. You may check en.wikipedia.org/wiki/Big_O_notation#Little-o_notation, if you will –  Woett Apr 15 '12 at 23:00
    
Ah I'm familiar with big-Oh, but I didn't know about little-Oh, thanks for the link. –  Roy T. Apr 16 '12 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? –  Roy T. Apr 16 '12 at 8:36

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.