Cycle Mathematics and Graph Theory

Multi-party barter networks discover cycles in directed credit graphs. When a directed cycle is detected, obligations across all edges in the cycle can be immediately cancelled without fiat currency changing hands.

This guide details the formal graph mechanics, adjacency representations, canonical rotation pruning, conflict-free set packing, and the strict mathematical proof of why NodeHash enforces K ≤ 3.

Directed Value Flow Graph Architecture

NodeHash models the non-monetary skill economy as a directed multigraph G = (V, E):

• Vertices (V): Every registered participant u ∈ V maintains a set of offered skills O(u) and a set of requested needs N(u).
• Directed Edges (E): A directed edge e = (u → v) exists if and only if u ≠ v, there exists a skill s such that s ∈ O(u), and s ∈ N(v). The edge carries an obligation weight w(e) representing delivery hours.
• Self-Loop Prevention: Self-edges (u → u) are strictly prohibited (∀ u, (u, u) ∉ E).

Dual Inverted Skill Index

Naive edge construction scans every pair of nodes in O(|V|²) operations. When thousands of nodes register, nested pair checks quickly degrade performance.

NodeHash prevents this by maintaining an in-memory dual inverted index:

1. Offer Index: Maps each skill identifier to its set of providers: s ↦ {u ∈ V | s ∈ O(u)}.
2. Need Index: Maps each skill identifier to its set of seekers: s ↦ {v ∈ V | s ∈ N(v)}.

When building adjacency lists, the engine intersects provider and seeker sets per skill. Graph compilation drops from O(|V|²) to O(|V| · (|O| + |N|) + |E|), completing in under 15 milliseconds across 500 active participants.

Adjacency Matrix Representation

Let A ∈ {0, 1}^(|V| × |V|) be the adjacency matrix of G, where A_{ij} = 1 if a directed edge exists from vertex v_i to vertex v_j, and 0 otherwise.

In algebraic graph theory, powers of the adjacency matrix reveal walk distributions. The diagonal entry (A^K)_{ii} equals the exact number of closed walks of length K starting and ending at vertex v_i. While matrix multiplication helps count walks, finding elementary cycles (paths with no repeated vertices except the start) requires bounded graph traversal.

Cycle Topologies: Bilateral (K=2) vs Trilateral (K=3)

NodeHash searches for elementary cycles across two specific topologies:

The Cycle Rotation Problem and Canonical Min-Vertex Ordering

In any directed graph, an elementary cycle of length K with vertices (v_0, v_1, ..., v_{K-1}) can be traversed starting from any of its K constituent nodes:

• C_0 = (v_0, v_1, ..., v_{K-1})
• C_1 = (v_1, v_2, ..., v_{K-1}, v_0)
• ...
• C_{K-1} = (v_{K-1}, v_0, ..., v_{K-2})

All K sequences describe the exact same physical trade ring. A naive search algorithm discovers each cycle K times, cluttering candidate queues, wasting memory, and burdening downstream matching pipelines.

The Canonical Min-Vertex Rule

NodeHash assigns each user a deterministic integer index based on lexicographical sorting of their unique identifier:

index(u) ∈ {0, 1, ..., |V| - 1}

When launching a bounded depth-first search from root vertex v_0, the engine enforces the canonical constraint:

∀ i ∈ {1, 2, ..., K - 1}, index(v_i) > index(v_0)

Mathematical Proof of Deduplication

1. Existence: Let C be any directed elementary cycle in G. The set of vertices in C contains a unique minimum index vertex:

   v_min = argmin_{v ∈ C} index(v)

2. Uniqueness: When the search root is v_0 = v_min, all subsequent vertices v_i ∈ C satisfy index(v_i) > index(v_0). Therefore, cycle C is guaranteed to be detected during the search rooted at v_min.
3. Exclusion & Branch Pruning: For any other starting root u ∈ C where u ≠ v_min, we have index(u) > index(v_min). As soon as the search path reaches v_min, the condition index(v_min) > index(u) evaluates to false. The engine prunes the exploration branch immediately.

This condition guarantees zero duplicate cycle rotations without post-search deduplication filters or memory-heavy hash tables.

Visualizing Canonical Rotation Pruning

The diagram below illustrates how three rotations of the same circular trade loop are evaluated. Only the rotation starting at the minimum index node is accepted; all others are pruned at branch exploration.

Disjoint Set Packing for Conflict-Free Settlement

In active economies, human time is scarce. Alice cannot commit her same 40 weekly hours to two different cycles simultaneously. If Alice appears in Cycle 1 and Cycle 2, settling both leads to scheduling failure and broken trade commitments.

NodeHash models this as Maximum-Weight Disjoint Set Packing:

1. Discover all candidate elementary cycles C_1, C_2, ..., C_m across the graph.
2. Compute a composite quality score S(C) for each cycle based on rating histories, skill proficiency alignment, and delivery velocity:

   S(C_1) ≥ S(C_2) ≥ ... ≥ S(C_m)

3. Initialize an empty set of committed traders: U_assigned ← ∅.
4. Iterate sequentially through the sorted candidate list:
   • If participants(C_j) ∩ U_assigned = ∅:
     • Accept cycle C_j for execution.
     • Update U_assigned ← U_assigned ∪ participants(C_j).
   • Otherwise, reject cycle C_j due to participant overlap.

Greedy set packing guarantees that executed trades never collide, providing traders with conflict-free execution contracts.

Strict Mathematical Proof: Why K ≤ 3 is Enforced

Why does NodeHash strictly cap cycle exploration at depth K ≤ 3? Why not permit cycles of length K = 4, 5, or 10?

Two mathematical laws govern cycle clearing: search latency scaling and multi-party default fragility. Below is the formal analysis demonstrating why K ≤ 3 is the optimal protocol bound.

1. Combinatorial Search Latency: O(|V|^K)

Let G = (V, E) have average out-degree d = |E| / |V|. A bounded depth-first search exploring cycles up to length K explores candidate paths up to depth K:

Search Complexity = O(|V| · d^(K - 1)) ≈ O(|V|^K)

Consider a medium marketplace with |V| = 1,000 active nodes and average out-degree d = 25:

• K = 2 (Bilateral): Exploration space: 1,000 × 25 = 25,000 checks. Completes in < 2 milliseconds.
• K = 3 (Trilateral): Exploration space: 1,000 × 25² = 625,000 checks. Completes in ≈ 15 milliseconds.
• K = 4 (Quadrilateral): Exploration space: 1,000 × 25³ = 15,625,000 checks. Takes ≈ 450 to 900 milliseconds.
• K = 5 (Pentagonal): Exploration space: 1,000 × 25⁴ = 390,625,000 checks. Exceeds 12 seconds of compute time.

Real-time matchmaking requires sub-second responsiveness. Beyond K = 3, computational latency scales exponentially, making interactive matchmaking infeasible.

2. Multi-Party Dispute and Default Fragility

Even if computing power were infinite, human coordination fragility imposes a strict ceiling on cycle length.

Let p ∈ (0, 1) be the independent probability that any single trade participant disputes delivery, defaults on milestones, or fails to deliver work on schedule.

In a circular barter loop of length K, clearing is atomic. If even one participant fails to deliver, the entire credit cancellation loop fractures, leaving upstream participants with unfulfilled obligations:

P_success(K) = (1 - p)^K

The probability of cycle failure or dispute is therefore:

P_dispute(K) = 1 - (1 - p)^K

Assume a baseline participant dispute rate of p = 5% (0.05). Let us observe how cycle dispute rates multiply as loop length K increases:

Synthesis: The K ≤ 3 Protocol Invariant

NodeHash selects K ≤ 3 as a hard protocol invariant because it optimizes the trade frontier:

• Liquidity Expansion: Moving from K = 2 to K = 3 increases matchable trade volume by over 400% in empirical benchmarks, dissolving bilateral deadlocks.
• Compute Tractability: K ≤ 3 keeps traversal latency under 20 milliseconds, enabling live browser previews and interactive matching.
• Fault Tolerance: Over 85% of cycles clear smoothly under realistic dispute assumptions, protecting honest participants from domino cancellations.

Test the Math Interactively

Experience these mathematical principles in action on our interactive graph canvas.