Skip to Content

), it may or may not be the case that the N1 vertices of G define a permutation of the integers 0,…,N.  When the N1 vertices (xi,yi) of G define a permutation of the integers 0,…,N, G will be termed “canonical”, and Wagner[1] has extended Hart’s results on N-free dim 2 posets so as to delimit precisely the set of possible canonical ordered DAGs (oDAGs).  (These include ordered trees with sets of vertices such as {(0,0),(1,3),(2,1),(3,2)}, ordered forests with sets of vertices such as {(0.2),(1.3),(2,0)(3,1)}, and oDAGS which are neither trees and forests, such as those with sets of vertices like {(0,0),(1,2),(2,1),(3,3)}.


In addition to Wagner’s demonstration that the “orderability” of a canonical oDAG arises from its “N-freeness”, Jamison has investigated the conditions under which a canonical oDAG will possess a novel kind of symmetry when plotted on a torus instead of in a plane.  To see intutively the nature of this symmetry, consider the canonical oDAG G with vertices {(0,0),(1,4),(2,1),(3,3),(4,2)}.  If these vertices are plotted in the plane in the usual way,, one can cut the plane along lines x = -1/2,  x = 9/2, y = -1/2, and y = 9/2, and after doing so, form a torus on which one line corresponds to the two lines x = -1/2 and x = 9/2, and one line corresponds to the two lines y = -1/2 and y = 9/2.  Then, one can find a way to recut the torus back into the plane so that the original vertices of G now appear in the plane as the symmetrical set of vertices {(0,1),(1,0),(2,2),(3,4),(4,3)} (or {(-2,-1),(-1,-2),(0,0),(1,2),(2,1)} after translation of origin.)


For Wagner’s and Jamison’s purposes, it is immaterial that in any canonical oDAG G with N+1 vertices, any vertex (xi,yi) of G can also be uniquely identified with an integer-valued point (pi,ti,di,si) in E4 lying in a hyperplane that satisfies the equation pi + ti + di + si = N, where: i) pi is the number of vertices (xj,yj) in G such that xj < xi and yj> yi; ii) ti is the number of vertices (xj,yj) in G such that xj > xi and yj< yi; iii) di is the number of vertices (xj,yj) in G such that xj < xi and yj< yi; iv) si is the number of vertices (xj,yj) in G such that xj > xi and yj> yj; v) xi = pi

d<sub>i</sub>; vi) y<sub>i</sub> = t<sub>i</sub>di.   


But inasmuch as the equation  pi + ti + di + si

= N implies that any oDAG will naturally generate a variety of hyperplane arrangements in the sense of Stanley ,  this equation is actually quite useful in the study of empirical phenomena  whose formal characterization requires the postulation of hierarchically-organized structures that contain both +opaque +and transparent substructures,  e.g. ordered trees that not only contain opaque subtrees from which one cannot remove any proper subtree, but also transparent subtrees  from which one can remove a proper subtree at will.   (As first observed by Chomsky , examples of such opacity abound in natural languages, as evidenced, for example, by the fact that speakers of English can say “Whose picture did you see?” but not “Whose did you see picture?“, even though they can and often do say “Whom did you see a picture of?” instead of “Of whom did you see a picture?“)


To see why the equation p + t + d + s = N implicitly generates hyperplane arrangements of potential interest to students of opacity in hierarchical structures, consider first the trivial hyperplane arrangement that arises because any non-trivial subtree of an ordered tree G is itself an ordered tree.  For example, consider the values of p, t, d, and s for the vertices of the “toroidally symmetric” ordered tree T mentioned above:


(x,y)                       p             t              d             s

(0,0)                       0              0              0              4

(1,4)                       0              3              1              0

(2,1)                       1              0              1              2

(3,3)                       1              1              2              0

(4,2)                       2              0              2              0


Just as all the vertices of T lie in a hyperplane normal to and passing through the point (N/4, N/4,N/4, N/4 ) = (1,1,1,1), so also do the vertices {(2,1), (3,3),(4,2)} of the single subtree T’ of T lie in a second hyperplane also normal to but passing through the point (12/4, 02/4, 12/4, 22/4) (because the vertices of T’ can be recoordinatized as {(0,0,0,2), (0,1,1,0,(1,0,1,0)} relative to an origin at (1,0,1,0) )  So T and T’ together define an hyperplane arrangement consisting of two hyperplanes that are parallel in the sense of being both normal to the same vector .


            More importantly, T and T’ are each bounded in E4 by an additional hyperplane arrangement that may readily be seen by considering what happens to the equation      p + t + d + s = N when p, t, d, and s each assume the minimum possible value of 0:        (p-N/3)(t-N/3)(d-N/3) = 0, (p-N/3)(t-N/3)(s-N/3) = 0, (p-N/3)(d-N/3)(s-N/3) = 0, and (t-N/3)(d-N/3)(s-N/3) = 0.  These equations imply that: i) T is itself bounded by a tetrahedron in E4; ii) we may consider any proper non-trivial subtree T’ of T to be bounded by a tetrahedron, once we have recoordinatized the vertices of T’ relative to a new origin at the root of T’.  And any such tetrahedron of course defines a hyperplane arrangement consisting of four planes in E4.</p>

To report this post you need to login first.

Be the first to leave a comment

You must be Logged on to comment or reply to a post.

Leave a Reply