Undip as a formal language

A formal language equivalent to undip, and its application to building hamiltonian planar cubic (i.e, trivalent) maps, is described in Shuffle of parenthesis systems and Baxter permutations by Robert Cori, Serge Dulucq, Gérard Viennot (1986):

"...hamiltonian cubic maps are planar maps with a hamiltonian circuit in which all vertices have degree three. In such a map any vertex is incident with only one edge not in the hamiltonian polygon, this edge may be inside the polygon or outside. Thus to build a "Hamiltonian rooted cubic map" one has to choose 2k vertices among the 2n (those incident with inside edges) then draw a planar map inside the polygon (it is easy to see that this can be done in C sub k [the kth Catalan number] ways) and a planar map outside. We have thus also an intuitive proof of the fact that the number of "hamiltonian rooted cubic maps with 2n vertices" is:


Their argument explains a surprisingly simple relation: the number of undip words of length 2n is given by the product of the nth Catalan number and its successor.

To share in the surprise it helps to know that finding hamiltonian circuits in trivalent graphs is sometimes difficult. The hamiltonian cycle problem is a special case of the traveling salesman problem obtained by setting the distance between two cities to a finite constant if they are adjacent and infinity otherwise. In fact the hamiltonian cycle problem in trivalent graphs is NP complete: it is known to be formally equivalent to finding boolean values of the variables that will make an arbitrary expression in symbolic logic evaluate as true (Garey, Johnson, and Tarjan, 1976.) Yet we garner from the above formula the exact aggregate number of rooted (i.e. choose a starting edge and a direction) hamiltonian circuits in planar trivalent maps with n vertices—though our posterity may never find them all.

It may seem a bit inelegant that we must count rooted hamiltonian circuits, thus counting each hamiltonian circuit multiple times—once for each way we could start and go around the circuit—but this kind of counting is very much attuned with a weaver's needs. If we are making a basket, especially a large one, it can matter very much the order in which it is built, so it is good to count our options.

Note that since this counting distinguishes ud and np (for example,) it presumes an orientation. Being a genus zero (planar) map guarantees that the surface our basket is embedded in is orientable. We must still choose one of the two possible orientations: i.e., we must specify which of the two sides of the embedding surface we are looking at. Only then are the baskets ud and np distinguishable.


UNDIP AS A FORMAL LANGUAGE

Starting from the empty word, every word in undip can be formed by a succession of two-letter insertions (ud or np)—between letters, at the beginning , or at the end of the word—and two-letter shuffles of pairs of adjacent left/right characters past each other. Furthermore, the result of such a process is always a word in undip. Therefore the insertion rules and the shuffle rule constitute the formation rules of undip.


THE LEFT AND RIGHT DYCK LANGUAGES

The subset of undip words that can spelled with just the letters u and d are clearly formed using only the ud insertion rule. Such a rule forms the Dyck language on {u, d}. We will call this subset of undip the left Dyck language. Similarly, the subset of undip words that can be spelled with just the letters n and p are called the right Dyck language.

The Dyck language is familiar to us in the ordinary rules for using parentheses. For example, a sequence of parentheses that would be valid in a mathematical expression, such as,

(()())()

can be formed starting from the empty word by successive insertions between characters, at the beginning, or the end of the word, of the two-character sequence ().


UNSHUFFLED UNDIP WORDS

Starting with some word in undip, say

uunddupd ,

the shuffle rule allows us, step by step, to gather the left characters to the front of the word and the right characters to the rear. The end result is an unshuffled undip word. For the word above such a possible sequence of shuffles is

uunddupd
uunddudp
uudndudp
uuddnudp
uuddundp
uuddudnp ,

resulting in the unshuffled word uuddudnp after five shuffle mutations.


DESCENDANCE FROM DYCK BASKETS

Since the anterior portion of an unshuffled word has been formed by ud insertions, it is a left Dyck word, and likewise the posterior portion of an unshuffled word is a right Dyck word. Since each of these portions is, in itself, an undip word, we can employ the converse of the rule that any undip word can be inserted into any other undip word, and thereby separate these two concatenated undip words:

uuddudnp = uuddud + np

Let's see the above process above in terms of the baskets the words describe. We began with the polyhedral (i.e., 3-connected) basket uunddupd and mutated it incrementally through a sequence of five shuffle mutations into the 2-connected basket

uuddudnp .

We then parted it into two baskets, one described by a left Dyck word, the other described by a right Dyck word, or, what we will call a left Dyck basket and a right Dyck basket.

Every step is reversible: we may now rejoin the two baskets and, one by one, invert all of the shuffle mutations until we regain the original basket.

Therefore: Every undip basket is descendant by a sequence of shuffle mutations from the union of a left Dyck basket and a right Dyck basket (either of which may be null.)

This slide show shows the descent of the basket above using paper twogs.