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

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