Generative Structural Theory v1.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality
- 1SD Lab LLC
Abstract
For a relation on four fixed labelled nodes whose undirected support is the complete graph K_4 (each of the six edges carrying one or both of its pairs; one-way edges allowed), this manuscript counts the strongly connected spanning sub-relations (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). Strong connectivity of any relation on the four nodes is characterized by its 14 outgoing cuts, and s is given by inclusion-exclusion over these cuts. Its 2^14 terms are grouped by the preorder that each family of cuts generates; the coefficient of a preorder is (-1)^(c - b) (b - 1)! when the order induced on its c equivalence classes is a disjoint union of b chains, and 0 otherwise, proved by two sign-reversing involutions. The inclusion-minimal strongly connected relations on four labelled nodes are classified into four kinds: directed 4-cycles (6), a directed 3-cycle with the fourth node joined to it by one two-way edge (24), two paths u -> x -> v and u -> y -> v with v -> u (12), and two-way spanning trees (16), 58 in all, with minimality, disjointness, counts and necessity proved separately; mu of a parent relation is the number of these contained in it, counted kind by kind. These parts hold for every relation on the four nodes. Using the K_4 support, every strongly connected parent relation contains a directed 4-cycle, so mc = 4, and the members with four pairs are its directed 4-cycles. For all twelve pairs s = 1606, mu = 58, mc = 4; without one pair 620, 33, 4; for a strongly connected relation with one pair on each edge, given in the text, 5, 2, 4. For all twelve pairs and one edge, the members holding a pair of that edge are counted directly by contraction and reached sets (1378); with the 228 members of K_4 with that edge removed, taken from v1.29 with the correspondence confirmed, they give 1606, in agreement with the cut inclusion-exclusion. K_4 with one edge removed lies outside the class and can have mc = 5 (v1.29). The values 58 and 1606 are listed in the literature as cited by the review side, and the existence of a Hamiltonian cycle in a strongly connected semicomplete digraph is known; v1.30 presents symbolic proofs for four nodes, the literature was not checked by the drafting side, and no novelty is claimed. The proofs and counts are presented as symbolic arguments, without machine enumeration or numerical computation on the relations studied. AI assistance was used in drafting and review, as detailed in the disclosures. The parent relations treated concretely are those with support K_4, with K_4 with one edge removed only as the check C1; relations on five or more nodes are not treated.
Related
- Generative Structural Theory v1.27 — Theta 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.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality}},
author = {Koji Okino},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23465432},
url = {https://zenodo.org/records/23465432},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generative Structural Theory v1.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality
AU - Koji Okino
PY - 2026
DA - 2026/10/19
PB - Zenodo
DO - 10.5281/zenodo.23465432
UR - https://zenodo.org/records/23465432
AB - For a relation on four fixed labelled nodes whose undirected support is the complete graph K_4 (each of the six edges carrying one or both of its pairs; one-way edges allowed), this manuscript counts the strongly connected spanning sub-relations (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). Strong connectivity of any relation on the four nodes is characterized by its 14 outgoing cuts, and s is given by inclusion-exclusion over these cuts. Its 2^14 terms are grouped by the preorder that each family of cuts generates; the coefficient of a preorder is (-1)^(c - b) (b - 1)! when the order induced on its c equivalence classes is a disjoint union of b chains, and 0 otherwise, proved by two sign-reversing involutions. The inclusion-minimal strongly connected relations on four labelled nodes are classified into four kinds: directed 4-cycles (6), a directed 3-cycle with the fourth node joined to it by one two-way edge (24), two paths u -> x -> v and u -> y -> v with v -> u (12), and two-way spanning trees (16), 58 in all, with minimality, disjointness, counts and necessity proved separately; mu of a parent relation is the number of these contained in it, counted kind by kind. These parts hold for every relation on the four nodes. Using the K_4 support, every strongly connected parent relation contains a directed 4-cycle, so mc = 4, and the members with four pairs are its directed 4-cycles. For all twelve pairs s = 1606, mu = 58, mc = 4; without one pair 620, 33, 4; for a strongly connected relation with one pair on each edge, given in the text, 5, 2, 4. For all twelve pairs and one edge, the members holding a pair of that edge are counted directly by contraction and reached sets (1378); with the 228 members of K_4 with that edge removed, taken from v1.29 with the correspondence confirmed, they give 1606, in agreement with the cut inclusion-exclusion. K_4 with one edge removed lies outside the class and can have mc = 5 (v1.29). The values 58 and 1606 are listed in the literature as cited by the review side, and the existence of a Hamiltonian cycle in a strongly connected semicomplete digraph is known; v1.30 presents symbolic proofs for four nodes, the literature was not checked by the drafting side, and no novelty is claimed. The proofs and counts are presented as symbolic arguments, without machine enumeration or numerical computation on the relations studied. AI assistance was used in drafting and review, as detailed in the disclosures. The parent relations treated concretely are those with support K_4, with K_4 with one edge removed only as the check C1; relations on five or more nodes are not treated.
ER -