Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality
- 1SD Lab LLC
Abstract
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 K_{2,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. The proofs and counts are presented as symbolic arguments, without machine enumeration. AI assistance was used in drafting and review, as detailed in the disclosures. Parent relations with an empty edge, more than three paths, paths of length 1 and general 2-connected blocks are not treated.
Related
- Generative Structural Theory v1.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality
- Generative Structural Theory v1.28 — Generalized Theta Relations with One-Way Edges: Exact Counting and Minimality
- Generative Structural Theory v1.29 — Generalized Theta Relations with a Direct Edge: Exact Counting and Minimality
- Generative Structural Theory v1.24 — Component-Level Minimality: Structural Decomposition and Counting
- Generative Structural Theory v1.31 — Bidirected K4 Subdivisions: Exact Counting and Minimality
BibTeX
@misc{okino2026generative,
title = {{Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality}},
author = {Koji Okino},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23461813},
url = {https://zenodo.org/records/23461813},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality
AU - Koji Okino
PY - 2026
DA - 2026/10/19
PB - Zenodo
DO - 10.5281/zenodo.23461813
UR - https://zenodo.org/records/23461813
AB - 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 K_{2,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. The proofs and counts are presented as symbolic arguments, without machine enumeration. AI assistance was used in drafting and review, as detailed in the disclosures. Parent relations with an empty edge, more than three paths, paths of length 1 and general 2-connected blocks are not treated.
ER -