Hypergraph Ontology

FLOW ALGEBRA
HYPERGRAPH ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Graph and Network Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/hypergraph-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed mathematical formalisation; source page text not independently verified.

1. ONTOLOGY IDENTITY
ontology_id: kireth:mathematical-entities:hypergraph
entity_type: Hypergraph
parent_type: GraphAndNetworkEntity
scope: finite and infinite hypergraphs, incidence structures, hyperedges, duality, traversal and optimisation

2. TYPED ENTITIES
Vertex: atomic member of a vertex set V
Hyperedge: identified member e of an edge collection E with incidence subset inc(e) subseteq V
Hypergraph: H = (V,E,inc), where inc:E -> P(V)
SimpleHypergraph: hypergraph with distinct incidence subsets for distinct hyperedges
MultiHypergraph: hypergraph permitting distinct edge IDs with equal incidence subsets
UniformHypergraph(k): forall e in E, |inc(e)| = k
Rank(H): sup {|inc(e)| : e in E}, when defined
Degree(v): |{e in E : v in inc(e)}| for finite incidence
IncidenceMatrix: B[v,e] = 1 iff v in inc(e), else 0
DualHypergraph: exchanges vertices and hyperedge IDs via incidence transposition

3. FOUNDATIONAL AXIOMS
A1: V is a set of vertices.
A2: E is a set of hyperedge identifiers.
A3: inc is a total mapping E -> P(V).
A4: Every hyperedge incidence is a subset of V.
A5: Empty hyperedges and isolated vertices are permitted by the general model; restricted subclasses may prohibit them.
A6: Hyperedges may contain more than two vertices; ordinary undirected graphs embed as 2-uniform hypergraphs.
A7: Hyperedge identity and incidence membership are distinct: two edge IDs may have the same vertex subset.

4. MATHEMATICAL OPERATIONS
incident(v,e) := v in inc(e)
adjacent(u,v) := exists e in E: u != v and {u,v} subseteq inc(e)
degree(v) := sum_{e in E} indicator(v in inc(e)) [finite E]
edge_size(e) := |inc(e)|
induced(H,S): vertices S subseteq V; hyperedges defined by an explicitly chosen convention (edge-contained or trace intersection)
trace(H,S): hyperedges inc(e) intersect S, with empty traces handled by declared policy
subhypergraph(H'): V' subseteq V, E' subseteq E, and incidence preserved or explicitly restricted

5. INVARIANTS AND IDENTITIES
For finite H: sum_{v in V} degree(v) = sum_{e in E} |inc(e)|.
For finite k-uniform H: sum_v degree(v) = k|E|.
For finite H: B is a |V| x |E| binary matrix.
For finite H: row sums of B are vertex degrees; column sums are hyperedge sizes.
For finite H: incidence duality transposes B.
A 2-uniform hypergraph with distinct unordered endpoint sets corresponds to a simple loopless undirected graph.

6. RELATIONSHIP ALGEBRA
Hypergraph HAS_VERTEX Vertex
Hypergraph HAS_HYPEREDGE Hyperedge
Hyperedge INCIDENT_TO Vertex
Hypergraph HAS_INCIDENCE_MATRIX IncidenceMatrix
Hypergraph MAY_HAVE_PROPERTY Uniformity
Hypergraph HAS_DUAL DualHypergraph
Hypergraph GENERALISES UndirectedGraph [under 2-uniform embedding]
Hypergraph RELATED_TO SetSystem
Hypergraph RELATED_TO BipartiteIncidenceGraph

7. INFERENCE RULES
R1: incident(v,e) and e in E => v in V.
R2: incident(u,e) and incident(v,e) and u != v => adjacent(u,v).
R3: forall e in E, |inc(e)|=k => k_uniform(H).
R4: distinct e1,e2 with inc(e1)=inc(e2) => parallel_hyperedges(H).
R5: finite(H) => total_incidence_count = sum_v degree(v) = sum_e edge_size(e).
R6: incidence_matrix(H)=B => incidence_matrix(dual(H))=transpose(B), under the stated dual construction.
R7: |inc(e)| > 2 => e cannot be represented as a single ordinary graph edge without information loss.

8. SEMANTIC DISTINCTIONS
Hypergraph != ordinary graph: hyperedges may connect any number of vertices.
Hyperedge != clique: clique expansion loses original hyperedge identity and grouping.
Hypergraph != bipartite incidence graph: the latter is a representation with separate vertex and hyperedge nodes.
Simple hypergraph != multihypergraph: the latter retains repeated incidence sets as distinct edges.
Uniform hypergraph != regular hypergraph: uniform constrains edge sizes; regular constrains vertex degrees.

9. VALIDATION
V1: verify every referenced vertex and hyperedge ID exists.
V2: verify inc(e) subseteq V for all e.
V3: verify claimed uniformity against every hyperedge.
V4: verify incidence matrix dimensions and binary entries.
V5: verify finite incidence counting identity when finite.
V6: do not infer a unique hypergraph from clique expansion alone.
V7: declare conventions for empty hyperedges, repeated hyperedges, and induced subhypergraphs.

10. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  mathematical_core: high
  source_page_alignment: unverified
  inferred_relationships: review_required
PROVENANCE:
  source_url: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/hypergraph-ontology.html
  derivation: mathematical ontology synthesis

11. SEMANTIC_EQUIVALENCE
Hypergraph ~ incidence set system [when hyperedge identities and incidence semantics are retained]
2-uniform simple hypergraph ~ simple loopless undirected graph [under standard correspondence]
Hypergraph ~ bipartite incidence representation [up to typed incidence-preserving isomorphism]

12. UPDATE_MODEL
version: 1.0
update_policy: preserve ontology_id; revise definitions with versioned provenance
breaking_changes: changes to incidence identity, empty-edge conventions, or induced-subhypergraph semantics

13. FLOW_HASH
algorithm: SHA-256
canonicalisation: UTF-8; LF line endings; normalised field ordering; exclude the hash value itself
status: compute on deployment from the final canonical payload

14. AI_CONSUMPTION
parse_mode: typed entity-relation-rule
reasoning: check preconditions before applying inferences
output_requirements: preserve hyperedge IDs, incidence structure, and declared conventions
safety: do not conflate pairwise adjacency with full hyperedge membership

END FLOW ALGEBRA