Suppose we were to take the plane, , and turn it into a graph – not the function plotting kind, the edge and vertex kind.
We let every point in the plane be a vertex, and we draw an edge between two vertices if they are at a distance of exactly from each other (Euclidean metric. We could take other metrics or other base spaces, but that is perhaps a topic for a further post).
We’ve now got a pretty formidable object! Uncountably many vertices and uncountably many edges at each vertex! But this graph is amenable enough after a little thought. Three quick ideas:
Suppose we were to take a finite alphabet of letters, say , and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:
and there are many of these. Let’s denote the set of length- words using the alphabet by .
What I am interested in now is “For a given and , what is the minimum length string of letters I can write down and still be sure that every word in appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.
contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,
are examples of optimal tours through and respectively, as they both have this property that each letter added after the first adds a previously unseen word.
Notice I’ve introduced the terminology tour for any string that contains all words in a given , with optimal tour being the tour that is of minimum possible length for that and .