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
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2010 at 15:18 | history | edited | Fiktor | CC BY-SA 2.5 |
Using comments to put the doubt
|
| Oct 20, 2010 at 10:42 | comment | added | Graham | We can show that this stronger statement is false, by considering the graph with distance 3 and 10 edges. On this graph, horizontal loops have distance at least 3, vertical loops distance at least 3, and diagonal loops distance at least 4. If the above conclusion were true, then because we had two classes of loops with minimum distance 3 and 4, we would have at least 12 edges, which is clearly false. This shows that there is something special about the fact that the minimum distance is the same for vertical and horizontal loops, and I don't see how this can be used in your outline. | |
| Oct 20, 2010 at 10:39 | comment | added | Graham | Fiktor, Many thanks for the attempt. Unfortunately, I believe that the hole is very difficult to fill. To illustrate this, let me present a slightly different question. Imagine the question specified that horizontal loops (both primal and dual) had to have length at least n, and that vertical loops (primal and dual) had to have length at least m (just pick two arbitrary classes of loop to label vertical and horizontal). Your argument would be exactly the same for this question, and if valid, would let us conclude that such a graph had at least mn edges. This conclusion is false (continued...) | |
| Oct 20, 2010 at 8:56 | comment | added | Fiktor | I don't understand, how is it related to the problem. It is about minimizing the number of edges. Minimal triangulation has 21 edge, while there is a solution with only 10 edges (as was shown by Graham). | |
| Oct 20, 2010 at 8:22 | comment | added | Gjergji Zaimi | For n=3, the minimal triangulation of a torus has 7 vertices... | |
| Oct 20, 2010 at 8:16 | history | answered | Fiktor | CC BY-SA 2.5 |