Timeline for how to get the coefficient of a special term in the expansion of the graph polynomial?
Current License: CC BY-SA 4.0
36 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2018 at 11:53 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 25 characters in body
|
| Jun 5, 2018 at 11:44 | comment | added | Carlo Beenakker | @fedja --- "how do you count those big sizes?" --- I found generating functions for $C_{2p,2q}$ with $p=1,2$ --- no idea whether these are known for larger $p$. | |
| Jun 5, 2018 at 11:43 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 8 characters in body
|
| Jun 5, 2018 at 11:35 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 18 characters in body
|
| Jun 4, 2018 at 20:23 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 34 characters in body
|
| Jun 4, 2018 at 20:13 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 244 characters in body
|
| Jun 4, 2018 at 16:25 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 77 characters in body
|
| Jun 4, 2018 at 15:54 | comment | added | j.c. | One reference for the connection between the coefficients of the graph polynomial and Eulerian orientations is Lemma 2.2 of "Colorings and orientations of graphs" by Alon and Tarsi cs.tau.ac.il/~nogaa/PDFS/chrom3.pdf . In particular, your guess holds true. | |
| Jun 4, 2018 at 14:58 | comment | added | fedja | @CarloBeenakker "for m and n both even equal the number of Eulerian orientations" That was exectly my starting point and then I got confused with cancellations in the odd cases a bit. But how do you count those for big sizes? OEIS gives no hint whatsoever. | |
| Jun 4, 2018 at 14:22 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 18 characters in body
|
| Jun 4, 2018 at 14:16 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 18 characters in body
|
| Jun 4, 2018 at 13:59 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 2 characters in body
|
| Jun 4, 2018 at 13:52 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 46 characters in body
|
| Jun 4, 2018 at 13:37 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Jun 4, 2018 at 13:28 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 31 characters in body
|
| Jun 4, 2018 at 13:20 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 31 characters in body
|
| Jun 4, 2018 at 13:18 | comment | added | fedja | @CarloBeenakker Found it. I missed some more cancellations. Indeed, $4\cdot 3^n$ it is. Looks like it is time to post now ;-) | |
| Jun 4, 2018 at 13:13 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 15 characters in body
|
| Jun 4, 2018 at 12:36 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
deleted 15 characters in body
|
| Jun 4, 2018 at 12:31 | comment | added | fedja | @CarloBeenakker OK, looking for ar error then. :) | |
| Jun 4, 2018 at 11:59 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 3 characters in body
|
| Jun 4, 2018 at 11:52 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 17 characters in body
|
| Jun 4, 2018 at 10:45 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 1 character in body
|
| Jun 4, 2018 at 10:29 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 224 characters in body
|
| Jun 4, 2018 at 10:24 | comment | added | Carlo Beenakker | @fedja -- using Mathematica, I find that the $3\times 6$ coefficient is 108. | |
| Jun 4, 2018 at 10:23 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 224 characters in body
|
| Jun 4, 2018 at 1:05 | comment | added | fedja | @Jacob.Z.Lee And yes, I agree that it is $0$ for odds. My stupidity, sorry for that. So, $2^{2n+1}+4$ for evens up to the sign. | |
| Jun 4, 2018 at 1:00 | comment | added | fedja | @Jacob.Z.Lee Then we diverge on $3\times 6$ for the first time. I predict $\pm 132$ and you $108$. I guess we should ask the computer who is right and if it is I, I'll post the argument, but if it is you, I'll look for a mistake in my reasoning. :-). I don't have any fancy CAS on my old laptop. Do you? | |
| Jun 4, 2018 at 0:55 | comment | added | Jacob.Z.Lee | @fedja In general, Let $G$ be the cartesian product graph $C_3\times C_{2n}$ and $P_G(x_1,x_2,\cdots, x_{6n})$ be the graph polynomial of $G$. I guess the coefficient of the term $x_1^2x_2^2\cdots x_{6n}^2$ in the expansion of the polynomial $P_G(x_1,x_2,\cdots, x_{6n})$ is $(-1)^{n-1} 3^{n}\times 4 $ for $ 3\times 2n$, the answer is $0$ for $3\times (2n-1)$. I know the pattern, but I can't prove its correctness. | |
| Jun 4, 2018 at 0:49 | comment | added | fedja | @Jacob.Z.Lee You are probably right for $3$ by odd (I missed the cancellations there). However for $3\times 4$ your formula gives $-12$, which is certainly wrong. | |
| Jun 4, 2018 at 0:48 | comment | added | Jacob.Z.Lee | @fedja In general, Let $G$ be the cartesian product graph $C_3\times C_{2n}$ and $P_G(x_1,x_2,\cdots, x_{6n})$ be the graph polynomial of $G$. I guess the coefficient of the term $x_1^2x_2^2\cdots x_{6n}^2$ is $(-1)^{n-1} 3^{n}\times 4 $ for $ 3\times 2n$, the answer is $0$ for $3\times (2n-1)$. I know the pattern, but I can't prove its correctness. | |
| Jun 3, 2018 at 23:17 | comment | added | fedja | @Jacob.Z.Lee Is there any pattern I believe that for $3\times m$ the answer is $2^{m+1}+4(-1)^m$ (again, up to the sign, which is enumeration dependent). The general $n\times m$ is still a mystery for me. | |
| Jun 3, 2018 at 22:38 | comment | added | Jacob.Z.Lee | @fedja Yes, the case will be more complicated when there are more vertices and edges. | |
| Jun 3, 2018 at 22:33 | comment | added | Jacob.Z.Lee | @Carlo Beenakker right answer. But I prefer to know how to calculate the answer out by hand. Is there any pattern in coefficient of the term in the expansion of the polynomial? | |
| Jun 3, 2018 at 21:42 | comment | added | fedja | Indeed, $36$ it is (plus or minus depends on how you enumerate the vertices). Is Mathematica able to do the $3\times 40$ tesselation? (the human answer is plus or minus $2^{41}+4$ but humans are error-prone, you know...) | |
| Jun 3, 2018 at 19:34 | history | answered | Carlo Beenakker | CC BY-SA 4.0 |