Timeline for How many inclusion preserving maps of subsets?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 15, 2017 at 16:52 | comment | added | Yaakov Baruch | @RichardStanley: hugely so. So now based on your formula, for $n=2k+1$, we can say that a lower bound is $>\big(\frac{k+1}{e}\big)^{{2k+1}\choose{k}}$ and obviously an upper bound is $\le (k+1)^{{2k+1}\choose{k}}$. (Notice that the ratio of logs of these bounds approaches 1 as $k$ grows, which makes them good enough to satisfy my original curiosity.) If you want to make this into an answer I'll gladly accept it. | |
| Feb 15, 2017 at 15:08 | comment | added | Richard Stanley | @YaakovBaruch: oops, you are right. This change just increases the lower bound. | |
| Feb 14, 2017 at 17:33 | comment | added | Yaakov Baruch | Both comments above are applicable to the general case, which can be regarded as a ${n-k}\choose{n-2k}$-regular bipartite graph with $2 {{n}\choose{k}}$ vertices. Thank you. | |
| Feb 14, 2017 at 17:21 | comment | added | Yaakov Baruch | @RichardStanley: I don't completely follow - shouldn't the $n$ in the paper correspond to ${n}\choose{k}$, the size of $\Sigma_k$, here? | |
| Feb 14, 2017 at 17:07 | comment | added | Richard Stanley | For $n=2k+1$ a lower bound is $\left(\frac{k^k}{(k+1)^{k-1}}\right)^n$. See homepages.cwi.nl/~lex/files/countpms2.pdf. | |
| Feb 14, 2017 at 16:46 | comment | added | Fedor Petrov | This estimate is probably very far from the real answer, but in the corresponding bipartite $(\Sigma_k,\Sigma_{k+1})$-graph (I consider the case $n=2k+1$) all vertices have degree $k+1$, thus it contains at least $(k+1)!$ perfect matchings (this is a general fact.) | |
| Feb 14, 2017 at 15:33 | history | asked | Yaakov Baruch | CC BY-SA 3.0 |