2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 15, 2012 at 16:48
  • $\begingroup$ @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 :/. $\endgroup$
    – Roy T.
    Commented Apr 15, 2012 at 21:21
  • 2
    $\begingroup$ @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 $\endgroup$
    – Woett
    Commented Apr 15, 2012 at 23:00
  • $\begingroup$ Ah I'm familiar with big-Oh, but I didn't know about little-Oh, thanks for the link. $\endgroup$
    – Roy T.
    Commented Apr 16, 2012 at 8:00
  • $\begingroup$ @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? $\endgroup$
    – Roy T.
    Commented Apr 16, 2012 at 8:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .