0
$\begingroup$

A function $f:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ overwhelms $g:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ if for any $k\in \mathbb{Z}_{\geq 1}$ the inequality $f(n)\leq g(n+k)$ holds only for finitely many $n\in\mathbb{Z}_{\geq 1}$.

For example $n\to n^2$ overwhelms $n\to n$.

Does the number of non-isomorphic posets of cardinality $n$ overwhelm the number of non-isomorphic groups of cardinality $n$?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ This is an interesting question, but you give no evidence that it’s research level. Partial information about these functions is not hard to come by. $\endgroup$
    – Kevin Carlson
    Commented May 2, 2021 at 12:45
  • 1
    $\begingroup$ In your deleted question today (where you initially compared groups vs topologies), I wrote the following comment, which seems still relevant here: Is there a reason to compare these two seemingly unrelated numbers? the second is highly sensitive to the prime decomposition of $n$ (high for powers of $2$, $=1$ for primes), the first increases with $n$. $\endgroup$
    – YCor
    Commented May 2, 2021 at 13:05
  • 2
    $\begingroup$ I’m voting to close this question: see @YCor's comment above and @‍Wojowu's comment on your very similar question. Especially notice that these questions were asked at nearly the same time. $\endgroup$
    – LSpice
    Commented May 2, 2021 at 14:36

1 Answer 1

Reset to default
9
$\begingroup$

On one hand, the number of groups of order $n$ is at most $2^{O((\log n)^3)}$ (see here). On the other hand, by considering posets which are disjoint unions of total orders, the number of posets of order $n$ is at least equal to the number $p(n)$ of partitions of $n$. Since $p(n)\gg 2^{\sqrt{n}}$, we get the desired result.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @firn You're right, I missed the $n$ in the base of the exponential. $\endgroup$
    – Wojowu
    Commented May 2, 2021 at 13:09
  • 2
    $\begingroup$ Not relevant to the question, but the number of posets of order $n$ is $2^{\frac{n^2}{4}+o(n^2)}$. $\endgroup$
    – Richard Stanley
    Commented May 2, 2021 at 14:45
  • $\begingroup$ @RichardStanley Thanks for the comment! Is that number for posets up to isomorphism or for a labelled set of elements? $\endgroup$
    – Wojowu
    Commented May 2, 2021 at 15:20
  • 3
    $\begingroup$ Either way, since $\log n! = o(\log 2^{n^2/4})$. $\endgroup$
    – Richard Stanley
    Commented May 3, 2021 at 13:23

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