[Math] Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long

co.combinatoricsgraph theorytopological-graph-theory

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!

Best Answer

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$.

Related Question