MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For referencing, I keep the original title and post and ask only about the simplest case (and forget the freeway with crossings for now).

Consider a trivalent graph, e.g. the dodecahedron or cube net. I like to draw it in braid fashion, i.e. (see pic below) with a closure (black), lanes (red) and some elements (U yellow, H blue, T green - yes, the naming is silly but I named H "H" long befor I "invented" T and U). The graph below would correspond to the word U1H3T2.
Of course the very simple graph of the pic can be drawn with less than 4 lanes. I want to know if there is a number n such that any trivalent graph can be drawn with maximally n lanes. E.g. surely n>2 because on 2 lanes you can't do pentagons with U,T,H. If yes, are one or even two elements of the set {U,T,H} actually superfluous?

Of course, my ultimative goal is to define an algebra in U,T,H (see old pic below) but these equations are NOT to be used for the question above! (Still, it would be fortituous if the answer is n=3 as all "natural" equations use maximally 3 lanes. Somehow, it must relate to Hamilton circuits.)


The question is analogous to that on the braid index of a knot. Here are again the allowed building blocks:


For example, the net of a dodecahedron can be drawn as a closure of a three lane freeway, just using "U" (and I, of course) pieces. (Using U+T+H probably can reduce the lane number to 2.)

Actually, these are several questions rolled into one:
AFAIK, the braid index problem is still unsolved. Does this change if (standard braid uses S+R) a) one allows H, b) one allows H but forbids R, c) one forbids H and R (surely some links then can't be drawn at all)? And before the freeway is tackled, better start with just the trivalent graph problem: Can all trivalent graphs be drawn with a finite lane number (or drawn at all), using only
a) U,T,H b) U,T c) U,H d) U?

share|cite|improve this question
The question is neither readable nor understandable for someone how is not already in the subject. Could you write a bit on the background, and explain the notation ? – DamienC May 5 '11 at 15:29
I am an expert on this topic, and I still find this question hard to read and understand. Is the blue in the pictures meaningful? What does "drawn at all" mean here? For G2 are you allowing sums/scalar multiples? (If so, the G2 version of the question is trivial...) Anyway, I think the question you're asking is whether any knotted trivalent graph can be written as the closure of a diagram with n strands at the bottom, n strands at the top, and n strands at every point in between except for small intervals where two of the strands have a T or U diagram (and the blue means nothing). – Noah Snyder May 5 '11 at 16:22
I realise it is only a convention but I would expect the labels H and U to be the other way around. – Bruce Westbury May 5 '11 at 19:24
If the experts are having trouble understanding it, the question is badly phrased. (It makes absolutely no sense to me, but that's neither here nor there...) I have voted to close, and I encourage the OP to modify and clarify accordingly. – Pete L. Clark May 5 '11 at 19:46
The new picture isn't any sort of obvious braid closure; is that really how you meant to close up the diagram? – Dylan Thurston May 7 '11 at 22:16
up vote 8 down vote accepted

I think that the question is asking whether planar trivalent graphs have bounded width when they are put in thin position. (This is "thin position" in the same sense as in knot theory, except in this case in 2-dimensional topology rather than 3-dimensional topology.) As you might expect, the answer is no. If the graph is a large mat made of hexagons, then you can show using the isoperimetric inequality that the width is at least $\Omega(\sqrt{v})$. On the other hand, there is a classic theorem of Lipton and Tarjan that every planar graph has width $O(\sqrt{v})$. So the correct answer is $\Theta(\sqrt{v})$ rather than $O(1)$.

share|cite|improve this answer
THX. I already feared lots of hexagons would spoil the fun. (I bet the answer essentially will be the same for the analogous question for tetravalent graphs.) – Hauke Reddmann May 14 '11 at 17:26

If I understand the question the answer depends on whether or not you include the relations. The question has G2 in the title and you have simplified the words of length two which implicitly suggests you are using relations. On the other hand there is no explicit mention of relations in the question.

If you do not have relations the answer is No. Counterexamples are given by taking a word that begins and ends with (your) H_1. Then remove the top half of H from the top left corner and the bottom half of H from the bottom right corner.

If you do have relations, or rather rewrite rules, and you only consider irreducible diagrams with no crossings then the answer is Yes, with U, T, H.

Why do you introduce R and S?

share|cite|improve this answer
R and S are for using in the most general (freeway) case. But I fear overgeneralizing has confused matters even more. I'm sorry that I can't express myself in a clear way - I'm no mathematician. @Noah - yes, that was exactly was I meant. @Pete - I'm a complete n00b to the site either - how do I close, delete or modify the question? – Hauke Reddmann May 6 '11 at 9:03
@Hauke: To edit, click the link that says 'edit' directly below your post. When you do so, please explain what you mean by the 'freeway problem', so we don't have to guess... – Dylan Thurston May 6 '11 at 9:46

Your Answer


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.