Timeline for How many upper sets in this decomposition of finite posets
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 23, 2019 at 13:56 | comment | added | Jens Renders | @RichardStanley I don't just want to compute these numbers, I'm interested in this alghorithm (and thus this counting problem) specifically. Showing that this is exponential is more usefull for me than giving an other algorithm that is quadratic (like computing the Möbius function). | |
| Mar 23, 2019 at 13:39 | comment | added | Richard Stanley | If you just want to compute the Euler characteristic quickly, then it is just one more than the Möbius function $\mu_{\hat{P}}(\hat{0},\hat{1})$, where $\hat{P}$ is $P$ with a minimal element $\hat{0}$ and maximal element $\hat{1}$ adjoined. This can be computed quickly from the defining recurrence for $\mu$. If you want such information as the Betti numbers, then there are several tools like discrete Morse theory and lexicographic shellability available. | |
| Mar 23, 2019 at 13:03 | history | migrated | from math.stackexchange.com (revisions) | ||
| Mar 13, 2019 at 16:22 | comment | added | Jens Renders | @darijgrinberg No, I'm asking about (set theoretically) distinct upper sets. There is no reasoning with isomorphy here. This makes it of course even worse than if I was asking about non-isomorphic upper sets. But I am not asking about all of them. A lot of upper sets will never be reached by this recursion. The difficulty is counting the ones we do reach, not how many we have in total (which is of course O(2^n)) | |
| Mar 13, 2019 at 16:16 | comment | added | Jens Renders | @JairTaylor Thanks for the tip! | |
| Mar 13, 2019 at 16:10 | comment | added | darij grinberg | Are you asking how many non-isomorphic upper ideals a poset with $n$ elements may have? I'm pretty sure that this number is exponential is $n$, since for a rectangle poset (= product of two chains) the upper ideals are in bijection with lattice paths counted by a binomial coefficient (and most of them are non-isomorphic -- in the sense that symmetry can only take a constant factor away from the asymptotics). | |
| Mar 13, 2019 at 16:07 | comment | added | Jair Taylor |
Just as an aside, you can speed up your code a bit by using if signature in visited instead of if signature in visited.keys() so that it hashes the input instead of looking through the whole list. This can make a big difference if there are a very large number of evaluations.
|
|
| Mar 13, 2019 at 11:15 | history | asked | Jens Renders | CC BY-SA 4.0 |