Timeline for Alternative proof for counting problem in graphs
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 13, 2013 at 22:52 | vote | accept | László Kozma | ||
| Jan 10, 2013 at 9:37 | history | edited | László Kozma | CC BY-SA 3.0 |
added 100 characters in body
|
| Jan 10, 2013 at 8:26 | answer | added | Aaron Meyerowitz | timeline score: 1 | |
| Jan 10, 2013 at 7:06 | comment | added | domotorp | I think you should define what you mean by (spanning) subgraph in the question to avoid misunderstandings. | |
| Jan 9, 2013 at 21:08 | comment | added | László Kozma | @Gerhard: An explicit injective mapping between the two sets would be nice. Or maybe just an induction on the number of edges of G. Or perhaps something resembling contraction-deletion, where the two quantities would have the same recurrence but would differ in the base cases. Or something else entirely :) | |
| Jan 9, 2013 at 20:28 | comment | added | Gerhard Paseman | Assuming the answer is yes, what would such a proof look like? How would it start? Perhaps a combinatorial injection is what you seek? Gerhard "Ask Me About Imaginary Proofs" Paseman, 2013.01.09 | |
| Jan 9, 2013 at 19:46 | comment | added | Aaron Meyerowitz | Without that one could have $H$ a single edge and $G$ a single edge plus 3 isolated vertices. then $8=D'(G,H) \not \leq D(G, \vec H)=2.$ | |
| Jan 9, 2013 at 17:00 | comment | added | László Kozma | No, by subgraph of G=(V,E) I meant a subgraph having vertex set V, so adding isolated vertices doesn't change the number of subgraphs. To be precise, I mean spanning subgraphs, i.e. subsets of E, just that I find spanning subgraph a bit ambiguous, but nevertheless, I changed to text to make it clearer. | |
| Jan 9, 2013 at 16:59 | history | edited | László Kozma | CC BY-SA 3.0 |
deleted 20 characters in body; added 11 characters in body
|
| Jan 9, 2013 at 15:35 | comment | added | Aaron Meyerowitz | Clearly isolated vertices are forbidden since adding $k$ more of them to $G$ would double the number of counted subgraphs $k$ times but not change the counted orientations. | |
| Jan 9, 2013 at 15:09 | history | asked | László Kozma | CC BY-SA 3.0 |