Skip to main content
deleted 81 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Denote by $F(n)$ the number of different partial orders on the set of cardinality $n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves likeWe may bound $cn^2$$F(n)$ from below as follows (the lower estimate, which we need,for simplicity I assume that $n$ is proved as followseven): take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patialpartial orders, and each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$$N^n/n!> \binom{N}{n}\geqslant F(n)\geqslant 2^{n^2/4}/n!$, sothus $N$ should grow at least exponentially$N>2^{n/4}$.

Denote by $F(n)$ the number of different partial orders on the set of cardinality $n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.

Denote by $F(n)$ the number of different partial orders on the set of cardinality $n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$. We may bound $F(n)$ from below as follows (for simplicity I assume that $n$ is even): take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ partial orders, and each isomorphism class is counted at most $n!$ times. So, $N^n/n!> \binom{N}{n}\geqslant F(n)\geqslant 2^{n^2/4}/n!$, thus $N>2^{n/4}$.

corrected a typo (m -> n)
Source Link
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

Denote by $F(n)$ the number of different partial orders on the set of cardinality $m$$n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.

Denote by $F(n)$ the number of different partial orders on the set of cardinality $m$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.

Denote by $F(n)$ the number of different partial orders on the set of cardinality $n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.

Post Made Community Wiki
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Denote by $F(n)$ the number of different partial orders on the set of cardinality $m$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.