Timeline for A strange sum over bipartite graphs
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6, 2012 at 22:33 | vote | accept | Brendan McKay | ||
| Mar 6, 2012 at 11:02 | history | edited | Brendan McKay | CC BY-SA 3.0 |
generalization
|
| Mar 6, 2012 at 10:11 | history | edited | Brendan McKay | CC BY-SA 3.0 |
give a generating function proof; added 4 characters in body
|
| Mar 5, 2012 at 22:13 | comment | added | Brendan McKay | @Mariano: Nice observations! | |
| Mar 5, 2012 at 20:56 | comment | added | Igor Rivin | Ah, I see @Kevin proved the exact thing in the answer... | |
| Mar 5, 2012 at 20:53 | comment | added | Igor Rivin | So, the statement is that the expected value of the product is $n!.$ I find it really hard to believe that there is not a a simple way to see this (on the other hand, I am not seeing it right now :() | |
| Mar 5, 2012 at 18:57 | answer | added | Kevin P. Costello | timeline score: 13 | |
| Mar 5, 2012 at 18:04 | comment | added | Mariano Suárez-Álvarez | The number of summands is $2^{n^2}$, as there are $n^2$ edges in the complete bipartite graph, and we are summing over its subsets. | |
| Mar 5, 2012 at 17:53 | comment | added | Igor Rivin | Out of curiosity, what is the average value of the product (I don't have the number of summands readily available, and you (@Brendan) probably do...) | |
| Mar 5, 2012 at 10:25 | comment | added | Mariano Suárez-Álvarez | (It is cute, though, how $2n$ of the factors of $2$ in the formula without the $q$s stay $2$s, while the other $n^2-2n$ become $(1+q)$s...) | |
| Mar 5, 2012 at 10:02 | comment | added | Mariano Suárez-Álvarez | An unsuccessful approach is to weigh each summand by the number $e(G)$ of edges in $G$: we get $$\sum_{G\subseteq K_{n,n}} ~ q^{e(g)}\prod_{v\in V(G)} (t-2d_G(v)) = 4^n n! q^n (q+1)^{n^2-2 n} L_n\left(-\frac{((q+1) t-2 n q)^2}{4 q}\right).$$ | |
| Mar 5, 2012 at 9:34 | comment | added | Mariano Suárez-Álvarez | A little playing with your sum shows that if you replace the appearance of n in the left hand side of your equation by a variable t, the right hand side becomes $2^{n^2}n!L_n(-(t-n)^2)$, with $L_n$ the $n$th Laguerre polynomial. Maybe this has a meaning? $${}$$ Extra points for introducing a $q$ somewhere in the left hand side and getting $q$-Laguerre polynomials on the right hand side! | |
| Mar 5, 2012 at 7:00 | history | asked | Brendan McKay | CC BY-SA 3.0 |