Timeline for Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 22, 2010 at 11:39 | comment | added | Graham | Ah - apologies then. I didn't mean to ask about face-width, but rather, as you suggest, edge-width of the dual graph. | |
| Oct 21, 2010 at 10:53 | comment | added | Tony Huynh | Face-width at least n is actually your third condition with 1 replaced by n. That is, every non-contractible curve in the surface intersects the graph at least n times. So, yes your graph has face-width 1. From this definition, we have that face-width $\leq$ edge-width because any short non-contractible curve in the graph yields a short non-contractible curve in the surface (just follow the edges in parallel). So, you might be asking about graphs of face-width at least $n$. Or, you might be asking about graphs with edge-width at least $n$, and whose duals have edge-width at least $n$. | |
| Oct 21, 2010 at 1:54 | comment | added | Graham | Tony, thanks for the response. If I understand correctly, you are only using the fact that the face-width is at least n, and not the edge-width condition. ie, using the second of my original conditions and not the first. Why is this graph not a counterexample to your claim? Consider a graph with a single vertex, and 2n edges from this vertex to itself, n of which are horizontal loops on the torus, and the other n of which are vertical loops. This graph has face-width n, and only 2n edges. Am I misunderstanding the definition of face-width, and this graph actually has face-width 1? | |
| Oct 20, 2010 at 16:40 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 22 characters in body; added 9 characters in body
|
| Oct 20, 2010 at 16:29 | history | answered | Tony Huynh | CC BY-SA 2.5 |