Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If we are given a graph embedded on a torus, with the following properties, what is the minimum number of edges it can have?

  • Any noncontractible loop is comprised of at least n edges.
  • Any noncontractible dual loop is comprised of at least n edges.
  • Any noncontractible loop drawn on the torus intersects the graph at least once.

(The third condition is just to rule out cases where we embed a small planar graph on the torus, and trivially satisfy the first two conditions, there being no noncontractible loops)

We use the following definitions:

  • A loop is a series of edges, with each consecutive pair sharing a (different) common vertex, and with the first and last sharing a common vertex. It is noncontractible if the path formed by tracing along these edges is noncontractible on the torus.

  • A dual loop is a series of edges, with each consecutive pair sharing a (different) common face, and with the first and last sharing a common face. The name is because these edges form a loop on the dual graph. Likewise, it is noncontractible if it is noncontractible on the torus.

I believe that the answer is $n^2$ for even n, $n^2 + 1$ for odd n. The equality case, I think, is a square lattice on the torus, but rather than identifying horizontal and vertical lines, as is usually done to put a grid on the torus, you identify lines at 45 degrees to the grid. (Or slightly off 45 degrees, if n is odd)

It seems like a simple statement, but I haven't been able to find out whether this is true.

Thanks for any help! Graham

Edit: Whoops - rather than face-width, the second condition is asking about the edge-width of the dual graph. Apologies for the confusion!

share|improve this question
1  
If I take two cycles of length $n$ glued together at a vertex, and embed them on the torus as two non-homotopic non-contractible curves, do I satisfy the conditions? It seems like (1) and (3) are satisfied, and probably (2) as well since the dual graph only has one vertex. Maybe you want the minimum number of edges of a graph of face-width (representativity) $n$? –  Tony Huynh Oct 20 '10 at 0:56
    
I would consider this graph to have lots of dual loops of length 1, in the same way as an edge from a vertex to itelf which wraps around the torus could form a (primal) loop of length 1. Thanks for pointing me to the correct terminology - yes, by condition (2), I mean that the graph has face-width n. (And condition (1), that the graph has edge-width 1.) –  Graham Oct 20 '10 at 1:40
    
The last comment should say edge-width n - apologies. –  Graham Oct 20 '10 at 1:41
add comment

2 Answers

There should be a nice proof, but here is a reference that proves something stronger and weaker. This paper by de Graaf and Schrijver proves that every graph embedded on the torus with face-width at least $n \geq 5$, contains the toroidal $\lfloor 2n/3 \rfloor$-grid as a minor. Note that the toroidal $\lfloor 2n/3 \rfloor$-grid has (almost) $8n^2/9$ edges. So any graph on the torus with face-width at least $n$ has at least (almost) $8n^2/9$ edges, which is pretty close to the conjectured answer of $n^2$.

share|improve this answer
    
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? –  Graham Oct 21 '10 at 1:54
1  
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$. –  Tony Huynh Oct 21 '10 at 10:53
    
Ah - apologies then. I didn't mean to ask about face-width, but rather, as you suggest, edge-width of the dual graph. –  Graham Oct 22 '10 at 11:39
add comment

Here is the idea of the proof that the number of vertices in such a graph is at least $n^2$. See step 7 for the hole in the proof. I believe it can be patched.
Edit: As was shown in comments there are a lot of problems with this attempt. I am in doubt whether it can be patched or not.

Step 1: Cut the graph at any shortest loop (its length $l\geq n$). You will get a graph on a cylinder (imagine it as a "vertical" cylinder) with a correspondence between edges and vertices on its bottom to edges and vertices at its top. Lets call these bottom edges as $e_1,\dots,e_l$ and top --- $e'_1,\dots,e'_l$.

Step 2: Take any shortest dual path between correspondent edges on the top and on the bottom of the cylinder. It corresponds to a noncontractible dual loop on the torus and its length $k\geq n$. Cut the cylinder at the vertices "just to the right of this path". Now we have a graph on the square with correspondence between vertices on its left to vertices on its right. Denote "left" vertices by $x_0,\dots, x_m$ and right by $x'_0,\dots, x'_m$, sorted from the bottom: $x_0$ and $x'_0$ are vertices at the bottom correspondent to $x_m$ and $x'_m$.

Step 3: Start $n$ dual paths $p_1,\dots,p_n$ at edges $e_1,\dots,e_n$. Assume $x=x_0$ are current left vertex and $x'=x'_0$ --- current right vertex.

Step 4: Suppose on this step $x=x_i$ is the current left vertex and $x'=x'_ j$ --- current right vertex. "Move up one of these vertices": if $i< j$ let $\widetilde x=x_{i+1}$ to be next current left vertex and if $j< i$ let $\widetilde x'=x'_ {j+1}$ to be the next current right vertex. In the case $i=j$ draw the shortest path from $x_{i+1}$ to $x'_ {i}$ and the shortest path from $x_{i}$ to $x'_ {i+1}$. At least one of them has length at least $n$. Choose it and let $\widetilde x= x_{i+1}$ or $\widetilde x'=x'_{i+1}$ correspondingly to the choice.

Step 5: Assume, that we have just defined $\widetilde x$ on step 4 (otherwise we have defined $\widetilde x'$ and this step should be rewritten correspondingly). Prolong $p_1,\dots,p_n$ to the shortest path from $\widetilde x$ to $x'$ avoiding intersections (all edges of $p_1,\dots,p_n$ should be different). To show it is possible define $d(v)$ to be a distance from vertex $v$ to $x'$ (length of the shortest path). Suppose last edge of $p_j$ joins vertices $v$ and $w$. Then $|d(v)-d(w)|=1$, since this edge is the part from the shortest path from $x$ to $x'$. Let $d_j=\min(d(v),d(w))$. On this step add to $p_j$ only edges connecting vertices of the same type (i.e. $|d(v)-d(w)|=1$ and $\min(d(v),d(w))=d_j$). Use only vertices between two shortest paths: between $\widetilde x$ and $x$ with $x'$. Note that all $d_j$ are different. This proves that $p_j$ will not intersect with others. Finally set $x=\widetilde x$.

Step 6: If $x\neq x_m$ or $x'\neq x'_m$ go to step 4. Otherwise go to step 7.

Step 7: Note that now we have $n$ dual paths $p_1,\dots,p_n$ from the bottom to the top of the square. All we need is to assure that they correspond to the cycles of the initial graph (because in this case each of these cycles has length of at least $n$). To achieve this, I believe, we should do step 5 more accurately.

share|improve this answer
    
For n=3, the minimal triangulation of a torus has 7 vertices... –  Gjergji Zaimi Oct 20 '10 at 8:22
    
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). –  Fiktor Oct 20 '10 at 8:56
    
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...) –  Graham Oct 20 '10 at 10:39
    
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. –  Graham Oct 20 '10 at 10:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.