Maximal node diagram

Recall that nodes in the subset diagram are sets of nodes from the original diagram, linked whenever each node in the tail subset joins some node in the head subset; paths arise from successive links. Call nodes in the original diagram points to distinguish them from nodes in the subset diagram. In the subset diagram of a general rule, multiple links can emanate from a single point, multiple links can also converge to a point; indeed this is the reason subset diagrams were invented, to ensure simple links between subsets.

For a surjective rule, however, only one path can run between a given pair of endpoints, one of whose consequences can be seen by factorizing a path between two nodes. Let the path x run from nodes U to V, continuing on to node via y (anticipating a variation of y).

Count the paths between points due to xy in two ways: Take as a unit class to eliminate ambiguity in the starting point, then either proceed directly to , or interrupt the path with a stopover at . The essential point is that there can be only one interrupted path. Now vary y, supposing only that it is a path of length p:

This equation expresses an average, so that the argument applying to averages of extreme quantities can be used once again: if V is a node of maximal cardinality, all the terms of the average must assume the same value.

Paths leading from a given unit class will not all reach maximum nodes; those which do will not necessarily do so immediately. Finiteness of the diagrams ensures that there is a short path --- shorter than the cardinality of the diagram --- leading from any node to the maximal node accessible to it. Once a maximal node has been reached, further links will trace out paths confined to a class of nodes of the same cardinality.

Since the de Bruijn diagram itself is connected, there is only one maximal class, irrespective of the unit class from which it was derived. The reason is that one can find paths which alternate between maximal nodes in the subset diagram and individual points in the de Bruijn diagram. yielding a derivation of any maximal node from any point, and of one maximal node from any other; thus the maximal class is connected, and there are maximal subsets containing any given unit class.

Not all paths lead from unit classes to the maximal class; the fate of paths from other subsets may also vary. When the subset in question is larger (setwise) than maximal (in particular, the full set) we know that its eventual images must remain larger than maximal; their images do not necessarily have to lead into the maximal class, however.

Harold V. McIntosh