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

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the GQ of order 2? Seems like it should be well known, since nearly every other parameter for that graph is known, but I can find no reference to cite.

share|improve this question
    
The crossing number of the Tutte-Coxeter graph is 13 and thus its genus will be less than or equal to 13. –  D. N. Mar 10 '14 at 6:59

2 Answers 2

According to sage, the genus is 4

sage: T = graphs.TutteCoxeterGraph()
sage: T.genus()
4
share|improve this answer

Really just a long comment with some pictures. An embedding onto a genus 4 surface can also be seen directly although in the end we probably need sage to establish the bound is sharp.

Here is a description of the graph followed by a picture (produced by sage),

{0: [1, 17, 29],1: [0, 2, 22],2: [1, 3, 9],3: [2, 4, 26], 4: [3, 5, 13], 5: [4, 6, 18], 6: [5, 7, 23], 7: [6, 8, 28], 8: [7, 9, 15], 9: [2, 8, 10], 10: [9, 11, 19], 11: [10, 12, 24], 12: [11, 29, 13], 13: [4, 14, 12], 14: [13, 15, 21], 15: [8, 14, 16], 16: [15, 17, 25], 17: [0, 16, 18], 18: [5, 19, 17], 19: [10, 20, 18], 20: [19, 21, 27], 21: [14, 20, 22], 22: [1, 23, 21], 23: [6, 24, 22], 24: [11, 23, 25], 25: [16, 24, 26], 26: [3, 25, 27], 27: [20, 26, 28], 28: [7, 29, 27], 29: [0, 28, 12]}Tutte-Coxeter graph

The edges [j,j+1 mod 30] form a $C_{30}$ subgraph this $C_{30}$ together with the edges $[0,17],[4,13],[20,27]$ and can be embedded in a disk $D_0$ such that the $C_{30}$ is embedded in the boundary of $D_0$. Attach a second disk $D_1$ to the boundary of $D_0$ in this disk embed the edges $[1,22],[5,18],[8,15]$. Likewise, attach disks $D_2$, $D_3$, $D_4$ with edge sets $[2,9],[12,29],[16,25]$; $[3,26],[6,23],[10,19]$; $[7,28],[11,24],[14,21]$. (The groups of 3 represent 3 non-intersecting edges in the graph that are not part of the specified $C_{30}$.)

Next embed this quotient space of the five disks into $\mathbb{R}^3$ and take a regular neighborhood N of this space. (Note we can choose an embedding such that the space has the cross section below.)

A graphic not made by sage

Actually, the graph embeds in the boundary of the neighborhood of this cross section, which is a genus 4 surface.

Furthermore, since the girth of the graph is 8, the Euler characteristic of any surface that this graph embeds into is less than $-2.75$, so by hand we can see the genus is either 3 or 4.

share|improve this answer

Your Answer

 
discard

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