Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality

GST v1.26 counted, for the bidirected theta relation -- two nodes u and v joined by three paths with no inner node in common, each of length at least 2 -- the strongly connected spanning sub-relations (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). This manuscript lets each edge of the parent relation carry one or both of its pairs. The parent relation is strongly connected if and only if on each path the one-way edges all point the same way, some path carries the whole direction from u to v and some path the whole direction from v to u. Since inclusion-minimality depends only on the sub-relation itself, the strongly connected and the inclusion-minimal sub-relations are exactly those of the bidirected relation that lie in the parent relation, so no new kind of minimal member arises. Counting on each path the restrictions in each of the four path states of v1.26 gives s = n_1 n_2 n_3 - PROD (b_i + g_i) - PROD (f_i + g_i) + g_1 g_2 g_3, where a two-way path has (f_i, b_i, d_i, g_i) = (2^(l_i) - 1, 2^(l_i) - 1, 1, l_i), a forward path with k_i one-way edges (2^(l_i - k_i), 0, 0, [k_i = 1]), a backward path the same with f and b exchanged, and n_i is their sum; mu follows in the same way from the two types of minimal member. One-way edges change s and mu but not mc: mc = l_1 + l_2 + l_3, one more than the number of nodes, for every strongly connected parent relation of the class. With v1.24 and v1.25, finite loop-free strongly connected components whose undirected blocks are bridges, cycles and such theta blocks are counted, and so are finite loop-free relations each of whose strongly connected components is of this kind. For K2,3 with one one-way edge, s = 147, mu = 13 and mc = 6; with one path one-way throughout, s = 56, mu = 7 and mc = 6. A related formula for the bidirected case is reported in a thesis by Cox (attributed there to Brown and Dilcher); its correspondence has not been checked, and no novelty is claimed. All results are argued by hand; no machine enumeration was made. Parent relations with an empty edge, more than three paths, paths of length 1 and general 2-connected blocks are not treated.