Timeline for Alternative proof for counting problem in graphs
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 13, 2013 at 22:52 | vote | accept | László Kozma | ||
| Jan 11, 2013 at 23:14 | comment | added | László Kozma | I think I understand (and believe:) the proof now. It is nice because it seems to make explicit where the "slack" is in the inequality. If I understand it correctly, the inequality is strict exactly if there is some $\vec S$ such that $emb(H,S)>emb(\vec H ,\vec S)$, which means that there is some edge of G that can be oriented differently by copies of $\vec H$ . | |
| Jan 11, 2013 at 14:36 | comment | added | Aaron Meyerowitz | For my (questionable) "proof" I am happy to give a vertex to vertex assignment but I do think that an edge embedding of a triangle in another graph uniquely determines the vertex assignment. I do have to think over my answer, but for $\vec H$ a directed triangle and $G$ a triangle, $D'(G,H)=1$ and there are $6$ embeddings of $H$ into that unique $S$. Also, $D(G,\vec H)=2$ or $3$ or $3$ depending on $\vec H.$ The number of triples is $\sum_{\vec G}emb(\vec H,\vec G)2^{|G|-|H|}=3\ 2^0+3\ 2^0=6$ in the first case and $1\ 2^0+1\ 2^0+1\ 2^0=3$ in the others. | |
| Jan 11, 2013 at 11:29 | comment | added | László Kozma | Is it really just for $H$ with isolated edges? Say, $\vec H$ is a directed triangle, and $G$ is a triangle. Then also there are 2 viable triples. | |
| Jan 11, 2013 at 7:12 | comment | added | Aaron Meyerowitz | You are correct, a single edge actually has $2|G|$ embeddings. I suppose that the embedding must say which vertices go to which (which also says which edge goes to which). However that is really only required when $H$ has one or more isolated edges. Otherwise, just the edge to edge map determines the vertex to vertex. So if $H$ consists of $k$ disjoint edges, then $| emb (H,H)|=k!2^k$. I'll think about it more. | |
| Jan 10, 2013 at 15:21 | comment | added | László Kozma | I think this will affect the second part as well, but not the third part. So the proof might still be correct, as we now need $k |emb(H,S)| 2^{|G|−|H|} \geq |emb(\vec H ,\vec S )| 2^{|G|−|H|}$, where $k \geq 1$. Is this correct? | |
| Jan 10, 2013 at 15:04 | comment | added | László Kozma | When you count the viable triples for a fixed embedding, shouldn't the count also depend on the number of isomorphic reorientations of $\vec H$? For example if both $G$ and $H$ consist of a single edge, the number of viable triples should be 2 (two orientations of G * one subset * one embedding), but the formula gives 1. | |
| Jan 10, 2013 at 8:26 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |