Tripartite Decompositions

Tripartite Decompositions

Trit: 0 (ERGODIC - coordinates decomposition)
Foundation: StructuredDecompositions.jl + GF(3) conservation
Principle: Every problem decomposes into 3 parts summing to 0 mod 3

Core Concept

A tripartite decomposition is a structured decomposition where:

1. The decomposition shape is a 3-clique (triangle)
2. Each bag is labeled with a trit ∈ {-1, 0, +1}
3. Adhesions preserve GF(3) conservation: Σ trits ≡ 0 (mod 3)

        MINUS (-1)
           ╱╲
          ╱  ╲
         ╱    ╲
        ╱  ⊗   ╲
       ╱________╲
 ERGODIC (0)   PLUS (+1)
 
 Conservation: (-1) + 0 + (+1) = 0 ✓

Mathematical Foundation

From StructuredDecompositions.jl

# A structured decomposition is a diagram d: ∫G → Span(C)
# where G is the decomposition shape and C is the target category

abstract type StructuredDecomposition{G, C, D} <: Diagram{id, C, D} end

struct StrDecomp{G, C, D} <: StructuredDecomposition{G, C, D}  
  decomp_shape ::G          # The shape (for tripartite: K₃)
  diagram      ::D          # The actual decomposition functor
  decomp_type  ::DecompType # Decomposition or CoDecomposition
  domain       ::C          # Source category
end

Tripartite Extension

using StructuredDecompositions
using Catlab

# Define the tripartite shape: K₃ (complete graph on 3 vertices)
@present SchTripartite(FreeSchema) begin
    (Minus, Ergodic, Plus)::Ob
    
    # Adhesions (edges of K₃)
    me::Hom(Minus, Ergodic)
    ep::Hom(Ergodic, Plus)
    pm::Hom(Plus, Minus)
    
    # Trit attributes
    trit::Attr(Minus, Int)   # Always -1
    trit::Attr(Ergodic, Int) # Always 0
    trit::Attr(Plus, Int)    # Always +1
end

@acset_type TripartiteShape(SchTripartite)

# Tripartite decomposition with GF(3) verification
struct TripartiteDecomp{C, D} <: StructuredDecomposition{TripartiteShape, C, D}
    base::StrDecomp{TripartiteShape, C, D}
    
    function TripartiteDecomp(base::StrDecomp)
        # Verify GF(3) conservation
        trits = [
            ob_map(base.diagram, :Minus).trit,   # -1
            ob_map(base.diagram, :Ergodic).trit, # 0
            ob_map(base.diagram, :Plus).trit     # +1
        ]
        @assert sum(trits) % 3 == 0 "GF(3) violation"
        new{typeof(base.domain), typeof(base.diagram)}(base)
    end
end

The 𝐃 Functor (Lifting Problems)

# From StructuredDecompositions.jl:
# 𝐃 : Cat_{pullback} → Cat
# Takes any category C with pullbacks to 𝐃C (structured decompositions over C)

# For tripartite decompositions, we lift computational problems:
function lift_problem(F::Functor, d::TripartiteDecomp)
    # F: C → FinSet^op is a sheaf (computational problem)
    # Returns: F applied to each bag, with sheaf condition on adhesions
    
    minus_solution = F(bag(d, :Minus))
    ergodic_solution = F(bag(d, :Ergodic))
    plus_solution = F(bag(d, :Plus))
    
    # Glue via adhesion spans
    return glue_tripartite(minus_solution, ergodic_solution, plus_solution, d)
end

Random Walk 3-at-a-Time

Decompose a set of N items into balanced triplets:

from dataclasses import dataclass
from typing import List, Tuple
import math

@dataclass
class TripartiteItem:
    name: str
    trit: int  # -1, 0, or +1
    data: any

class TripartiteDecomposer:
    """Decompose items into GF(3)-balanced triplets."""
    
    def __init__(self, seed: int):
        self.rng = SplitMix64(seed)
    
    def decompose(self, items: List[TripartiteItem]) -> List[Tuple]:
        """Random walk 3-at-a-time through items."""
        remaining = list(items)
        triplets = []
        
        while len(remaining) >= 3:
            # Select 3 items via PRNG
            selected = []
            for _ in range(3):
                idx = self.rng.next() % len(remaining)
                selected.append(remaining.pop(idx))
            
            # Check GF(3) conservation
            trit_sum = sum(item.trit for item in selected) % 3
            conserved = (trit_sum == 0)
            
            triplets.append((selected, conserved))
        
        # Handle remainder (incomplete triplet)
        if remaining:
            triplets.append((remaining, None))
        
        return triplets
    
    def entropy(self, items: List[TripartiteItem]) -> float:
        """Calculate Shannon entropy of trit distribution."""
        counts = {-1: 0, 0: 0, +1: 0}
        for item in items:
            counts[item.trit] += 1
        
        total = len(items)
        H = 0.0
        for count in counts.values():
            if count > 0:
                p = count / total
                H -= p * math.log2(p)
        return H

Skill Allocation Example

From TRIPARTITE_AGENTS.md:

┌─────────────────────────────────────────────────────────────────────┐
│  MINUS (-1)          ERGODIC (0)           PLUS (+1)               │
│  Purple, 270°        Cyan, 180°            Orange, 30°             │
│                                                                     │
│  bisimulation-game   unwiring-arena        gay-mcp                 │
│  spi-parallel-verify acsets                triad-interleave        │
│  polyglot-spi        skill-dispatch        world-hopping           │
│  structured-decomp   bumpus-narratives     cognitive-superpos      │
└─────────────────────────────────────────────────────────────────────┘

Each agent receives skills matching its polarity. The sum is always 0.

FPT Algorithms

Tripartite decompositions enable Fixed-Parameter Tractable algorithms:

# 3-coloring is decidable in O(3^w * n) where w = treewidth
# For tripartite shape, w = 2 (K₃ has treewidth 2)

function decide_3colorable(G::Graph, decomp::TripartiteDecomp)
    # Lift 3-coloring sheaf to decomposition
    coloring_sheaf = Functor(Graph, FinSet) do g
        # Return set of valid 3-colorings
        all_colorings(g, 3)
    end
    
    # Apply 𝐃 functor
    lifted = 𝐃(coloring_sheaf, decomp)
    
    # Check if limit is non-empty (solution exists)
    return !isempty(limit(lifted))
end

Dynamic Programming Connection

Tripartite decomposition fixes DP failures:

Color Integration

Each bag gets a deterministic color:

from gay import SplitMixTernary

def color_tripartite(seed: int):
    gen = SplitMixTernary(seed)
    return {
        'minus': gen.color_at(0),    # H ∈ [180°, 300°)
        'ergodic': gen.color_at(1),  # H ∈ [60°, 180°)
        'plus': gen.color_at(2)      # H ∈ [0°, 60°) ∪ [300°, 360°)
    }

Gluing via Adhesions

function glue_tripartite(minus, ergodic, plus, decomp)
    # Adhesion spans connect bags
    me_span = adhesionSpan(decomp, :me)  # Minus ← Apex → Ergodic
    ep_span = adhesionSpan(decomp, :ep)  # Ergodic ← Apex → Plus
    pm_span = adhesionSpan(decomp, :pm)  # Plus ← Apex → Minus
    
    # Pullback along adhesions
    me_glued = pullback(minus, ergodic, me_span)
    ep_glued = pullback(ergodic, plus, ep_span)
    pm_glued = pullback(plus, minus, pm_span)
    
    # Final result is limit of glued diagram
    return limit(FreeDiagram([me_glued, ep_glued, pm_glued]))
end

Validation

# Verify a tripartite decomposition
function verify_tripartite(decomp)
    bags = [bag(decomp, :Minus), bag(decomp, :Ergodic), bag(decomp, :Plus)]
    trits = [b.trit for b in bags]
    
    @assert sum(trits) % 3 == 0 "GF(3) violated"
    @assert length(adhesionSpans(decomp)) == 3 "Must have 3 adhesions"
    
    return true
end

Usage Example

using StructuredDecompositions
using Catlab

# Decompose a skill validation problem
skills = [
    Skill("julia-gay", -1),      # Missing SKILL.md
    Skill("acsets", +1),         # Content overflow  
    Skill("mcp-tripartite", 0),  # YAML error
]

# Create tripartite decomposition
decomp = TripartiteDecomp(
    StrDecomp(K3_graph(), 
        FinDomFunctor(
            Dict(:Minus => skills[1], :Ergodic => skills[3], :Plus => skills[2]),
            Dict(:me => span_me, :ep => span_ep, :pm => span_pm)
        )
    )
)

# Verify and solve
@assert verify_tripartite(decomp)
solutions = lift_problem(validation_sheaf, decomp)

Canonical Triads

structured-decomp (-1) ⊗ tripartite-decompositions (0) ⊗ gay-mcp (+1) = 0 ✓
bisimulation-game (-1) ⊗ entropy-sequencer (0) ⊗ triad-interleave (+1) = 0 ✓
spi-parallel-verify (-1) ⊗ acsets (0) ⊗ world-hopping (+1) = 0 ✓

See Also

• structured-decomp - FPT via tree decompositions
• gay-mcp - Deterministic color generation
• entropy-sequencer - Information-gain ordering
• triad-interleave - 3-stream parallel execution