ACSets (Attributed C-Sets): Algebraic databases with Specter-style bidirectional navigation. Category-theoretic formalism for relational databases.
/plugin marketplace add plurigrid/asi/plugin install plurigrid-asi-skills@plurigrid/asiThis skill inherits all available tools. When active, it can use any tool Claude has access to.
"The category of simple graphs does not even have a terminal object!" — AlgebraicJulia Blog, with characteristic ironic detachment
ACSets ("attributed C-sets") are a family of data structures generalizing both graphs and data frames. They are an efficient in-memory implementation of a category-theoretic formalism for relational databases.
C-set = Functor X: C → Set where C is a small category (schema)
┌─────────────────────────────────────────────────────────────┐
│ Schema (Small Category C) │
│ ┌─────┐ src ┌─────┐ │
│ │ E │───────▶│ V │ │
│ │ │ tgt │ │ │
│ └──┬──┘───────▶└─────┘ │
│ │ │
│ │ A C-set X assigns: │
│ │ X(V) = set of vertices │
│ │ X(E) = set of edges │
│ │ X(src): X(E) → X(V) │
│ │ X(tgt): X(E) → X(V) │
└─────────────────────────────────────────────────────────────┘
using Catlab.CategoricalAlgebra
@present SchGraph(FreeSchema) begin
V::Ob
E::Ob
src::Hom(E,V)
tgt::Hom(E,V)
end
@acset_type Graph(SchGraph, index=[:src,:tgt])
@present SchSymmetricGraph <: SchGraph begin
inv::Hom(E,E)
compose(inv,src) == tgt
compose(inv,tgt) == src
compose(inv,inv) == id(E)
end
@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])
@present SchWeightedGraph <: SchGraph begin
Weight::AttrType
weight::Attr(E, Weight)
end
@acset_type WeightedGraph(SchWeightedGraph, index=[:src,:tgt]){Float64}
Integrate with Music Topos 3-coloring:
# Map ACSet parts to trits for GF(3) conservation
function acset_to_trits(g::Graph, seed::UInt64)
rng = SplitMix64(seed)
trits = Int[]
for e in parts(g, :E)
h = next_u64!(rng)
hue = (h >> 16 & 0xffff) / 65535.0 * 360
trit = hue < 60 || hue >= 300 ? 1 :
hue < 180 ? 0 : -1
push!(trits, trit)
end
trits
end
# Verify conservation: sum(trits) ≡ 0 (mod 3)
function gf3_conserved(trits)
sum(trits) % 3 == 0
end
Since Catlab PR #990, @acset_colim exposes name→part bindings. Combine with Gay.jl for:
using Gay
# Build ACSet with named parts
result, bindings = @acset_colim SchGraph begin
e::E
v1::V; v2::V
src(e) == v1
tgt(e) == v2
end
# Color each named part deterministically
seed = 0x114514
colors = Dict{Symbol, String}()
for (name, (ob, idx)) in bindings
colors[name] = Gay.color_at(seed, idx) # deterministic hex
end
# => Dict(:e => "#A855F7", :v1 => "#3B82F6", :v2 => "#10B981")
Modality 1: Different seeds (parallel verification)
seeds = [0x1, 0x2, 0x3] # Three independent streams
colors_per_seed = [Gay.palette(s, length(bindings)) for s in seeds]
# XOR guarantee: if all three agree on structure, computation is stable
# Divergence → indicates floating-point or algorithmic instability
Modality 2: Same seed, staggered indices (convergence test)
seed = 0x114514
# Run same computation 3 times, color at indices 1, 2, 3
c1 = compute_and_color(data, seed, index=1)
c2 = compute_and_color(data, seed, index=2)
c3 = compute_and_color(data, seed, index=3)
# Convergence: c1 == c2 == c3 within bounded iterations → stable
# Divergence: colors differ → numerical instability detected automatically
# Empty block produces initial object (fixed in PR #990)
init, _ = @acset_colim SchGraph begin end # ∅
# Initial object gets neutral/zero color (the "0" in GF(3))
neutral_color = Gay.color_at(seed, 0) # or special "initial" marker
struct ColoredACSet{T}
acset::T
bindings::Dict{Symbol, Tuple{Symbol, Int}}
colors::Dict{Symbol, String}
seed::UInt64
end
function colored_acset_colim(schema, seed, block)
acset, bindings = @acset_colim schema block
colors = Dict(name => Gay.color_at(seed, idx)
for (name, (_, idx)) in bindings)
ColoredACSet(acset, bindings, colors, seed)
end
# Lookup by name → part index → color (all directions)
# name → color: ca.colors[:v1]
# color → name: findfirst(==(hex), ca.colors)
# name → part: ca.bindings[:v1][2]
function detect_instability(f, input, seed; tolerance=3)
"""
Run f three times with same seed at staggered indices.
If colors diverge beyond tolerance, flag instability.
"""
results = [f(input) for _ in 1:3]
colors = [Gay.color_at(seed, i) for i in 1:3]
# Compare results - if they should be identical but aren't,
# the divergent colors make the instability visually obvious
for i in 1:3, j in i+1:3
if results[i] ≠ results[j]
@warn "Instability detected" color_i=colors[i] color_j=colors[j]
return false
end
end
true
end
This integrates the semantic naming from PR #990 with Gay.jl's deterministic coloring to create self-validating, visually debuggable ACSet constructions.
Inspired by Nathan Marz's Specter library, navigate ACSets with paths that work for both select AND transform.
From Marz: "comp-navs is fast because it's just object allocation + field sets"
# What comp_navs actually does:
comp_navs(a, b, c) = ComposedNav([a, b, c]) # That's it!
# No compilation, no interpretation, no optimization
# Just: allocate struct, set field, done
# All work happens at traversal via CPS:
nav_select(nav1, data,
r1 -> nav_select(nav2, r1,
r2 -> nav_select(nav3, r2, identity)))
This means:
using SpecterACSet
# Navigate morphism values
acset_field(:E, :src) # All source vertex IDs
acset_field(:E, :tgt) # All target vertex IDs
# Filter parts by predicate
acset_where(:E, :src, ==(1)) # Edges where src == 1
# Navigate all parts of an object
acset_parts(:V) # All vertex IDs
acset_parts(:E) # All edge IDs
g = @acset Graph begin V=4; E=3; src=[1,2,3]; tgt=[2,3,4] end
# Select: get all source vertices
select([acset_field(:E, :src)], g) # → [1, 2, 3]
# Transform: shift all targets (same path!)
g2 = transform([acset_field(:E, :tgt)], t -> mod1(t+1, 4), g)
select([acset_field(:E, :tgt)], g2) # → [3, 4, 1]
Navigate the category of elements using paths:
# ∫G objects: (Ob, part_id) pairs
# Navigate to all elements
select([elements_of(:V)], g) # → [(V,1), (V,2), (V,3), (V,4)]
# Navigate morphism structure
select([elements_of(:E), incident_to(:src, 1)], g) # Edges from vertex 1
# ACSet → Sexp → Navigate → Transform → Sexp → ACSet
sexp = sexp_of_acset(g)
# Navigate sexp to find all morphism names
morphism_names = select([SEXP_CHILDREN, sexp_nth(1), ATOM_VALUE], sexp)
# Roundtrip back to ACSet
g2 = acset_of_sexp(Graph, sexp)
From Issue #7, implement functional patterns:
| Function | Description | Example |
|---|---|---|
map | Transform parts | map(g, :E) do e; ... end |
filter | Select parts by predicate | `filter(g, :V) { |
fold | Aggregate over parts | fold(+, g, :E, :weight) |
# From Issue #89: Open versions of InterType ACSets
using ACSets.OpenACSetTypes
# Create open ACSet with exposed ports
@open_acset_type OpenGraph(SchGraph, [:V])
# Compose via pushout
g1 = OpenGraph(...) # ports: v1, v2
g2 = OpenGraph(...) # ports: v3, v4
g_composed = compose(g1, g2, [:v2 => :v3])
The category of simple graphs does not even have a terminal object. Under the standard definition (symmetric, irreflexive edge relation), there's no "universal" graph that every other graph maps to uniquely. This reveals hidden assumptions in the simple graph model.
Simple graph: G = (V, E) where E is a binary relation on V that is:
Category theorist's graph: G consists of:
This allows:
A C-set is a functor X: C → Set where C is a small category (schema).
Schema C (small category) C-set X (functor C → Set)
────────────────────────── ─────────────────────────
Objects c ∈ C ────▶ Sets X(c)
Morphisms f: c → d ────▶ Functions X(f): X(c) → X(d)
| Term | Definition |
|---|---|
| C-set | Functor C → Set (copresheaf) |
| Presheaf | Functor C^op → Set (contravariant) |
| Category action | C-set generalizes G-set (group action) |
The schema Sch(Graph) is the category with:
┌───┐ src ┌───┐
│ E │───────▶│ V │
│ │ tgt │ │
└───┘───────▶└───┘
A graph G is a Sch(Graph)-set, meaning:
using Catlab.CategoricalAlgebra
using Catlab.Graphs, Catlab.Graphics
# Create empty graph and add parts
g = Graph()
add_parts!(g, :V, 3)
add_parts!(g, :E, 4, src=[1,2,2,3], tgt=[2,3,3,3])
# Query incident edges (uses index)
incident(g, 3, :tgt) # => [2, 3, 4]
# Graphs.jl-style convenience interface
g2 = Graph()
add_vertices!(g2, 3)
add_edges!(g2, [1,2,2,3], [2,3,3,3])
# Visualization
to_graphviz(g, node_labels=true, edge_labels=true)
The index=[:src,:tgt] parameter creates inverse lookups:
@acset_type Graph(SchGraph, index=[:src,:tgt])
# Without index: O(|E|) to find edges incident to vertex
# With index: O(k) where k = number of incident edges
The schema for symmetric graphs extends the graph schema with an involution:
┌───┐ src ┌───┐
│ E │───────▶│ V │
│ │ tgt │ │
│ │───────▶│ │
│ │ inv │ │
│ │◀──────▶│ │
└───┘ └───┘
Subject to equations:
inv ⨟ src = tgt
inv ⨟ tgt = src
inv² = id_E
For every edge e ∈ G(E):
e.inv.src = e.tgt (inverted edge starts where original ends)e.inv.tgt = e.src (inverted edge ends where original starts)e.inv.inv = e (involution is self-inverse)@present SchSymmetricGraph <: SchGraph begin
inv::Hom(E,E)
compose(inv,src) == tgt
compose(inv,tgt) == src
compose(inv,inv) == id(E)
end
@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])
# Create symmetric 4-cycle
g = SymmetricGraph()
add_vertices!(g, 4)
add_edges!(g, [1,2,3,4], [2,3,4,1])
# Creates 8 edges: 4 original + 4 inverses
Only src needs indexing. Target queries use: incident(g, v, :tgt) = incident(g, v, :src) .|> (e -> g[e, :inv])
Half-edges are paired by involution rather than having distinct source/target:
Schema Sch(HGraph):
┌───┐ vertex ┌───┐
│ H │─────────▶│ V │
│ │ inv │ │
│ │◀────────▶│ │
└───┘ └───┘
Equation: inv² = id_H
@present SchHalfEdgeGraph(FreeSchema) begin
V::Ob
H::Ob
vertex::Hom(H,V)
inv::Hom(H,H)
compose(inv, inv) == id(H)
end
@acset_type HalfEdgeGraph(SchHalfEdgeGraph, index=[:vertex])
Fixed points h·inv = h are dangling edges — half-edges not paired with others, left at the boundary. Distinct half-edges h ≠ h' with h·inv = h' and same vertex are self-loops.
g = HalfEdgeGraph(3)
add_edges!(g, [1,2,3], [2,3,1]) # 6 paired half-edges
add_dangling_edges!(g, [1,1,3]) # 3 dangling half-edges (fixed points)
Functor F: Sch(SGraph) → Sch(HGraph):
V ↦ V
E ↦ H
src ↦ vertex
tgt ↦ inv ⨟ vertex
inv ↦ inv
This is an isomorphism (invertible). The two perspectives are mathematically equivalent but have different interpretations.
A rotation system adds a permutation σ on half-edges where cycles = vertices:
@present SchRotationGraph <: SchHalfEdgeGraph begin
σ::Hom(H,H)
compose(σ, vertex) == vertex # cycles stay at same vertex
end
The schema Sch(RotSys) with just H, α (involution), σ (permutation) is a group — making rotation systems group actions.
Key theorem: Rotation systems ↔ cellular embeddings in oriented surfaces (1-1 correspondence).
A reflexive graph has a distinguished self-loop at each vertex:
┌───┐ src ┌───┐ refl
│ E │───────▶│ V │───────▶│ E │
│ │ tgt │ │
└───┘───────▶└───┘
Equations:
refl ⨟ src = id_V
refl ⨟ tgt = id_V
@present SchReflexiveGraph <: SchGraph begin
refl::Hom(V,E)
compose(refl, src) == id(V)
compose(refl, tgt) == id(V)
end
A homomorphism α: X → Y of C-sets is a natural transformation:
For each object c ∈ C: function α_c: X(c) → Y(c)
For each morphism f: c → d: naturality square commutes
X(c) ──α_c──▶ Y(c)
│ │
X(f) Y(f)
▼ ▼
X(d) ──α_d──▶ Y(d)
Graph homomorphism: vertex map + edge map preserving src/tgt.
Reflexive graph homomorphism: additionally preserves refl, so can "collapse" edges onto reflexive loops — enables quotient operations.
Products computed pointwise: (G × H)(c) = G(c) × H(c)
| Type | Product Name | Behavior |
|---|---|---|
| Graph | Categorical product | Disconnected diagonal paths |
| ReflexiveGraph | Categorical product | Grid with connections (reflexive loops fill gaps) |
| SymmetricGraph | Direct/tensor product | May split into components (bipartite → 2 components) |
| SymmetricReflexiveGraph | Strong product | Full grid connectivity |
Box product (graph theorist's "Cartesian product"): Pushout construction
function box_product(g::T, h::T)
g₀, h₀ = T(nv(g)), T(nv(h)) # discrete subgraphs
# ... pushout of inclusions with product projections
end
Terminal graph = self-loop.
This makes reflexive graphs more "geometric" — they discretize continuous spaces properly.
Sub-C-sets as propositions, logical connectives derived from adjoints.
| Connective | Definition | Meaning |
|---|---|---|
| A ∧ B | Right adjoint of Δ | Greatest lower bound (meet) |
| A ∨ B | Left adjoint of Δ | Least upper bound (join) |
| ⊤ | Right adjoint of ! | Top element (full subgraph) |
| ⊥ | Left adjoint of ! | Bottom element (empty) |
| B ⇒ C | Right adjoint of (−) ∧ B | Implication (exponential) |
| ¬A | A ⇒ ⊥ | Negation (Heyting) |
¬A (not-A, conservative): x ∈ ¬A iff no element reachable from x is in A
x ∈ (¬A)(c) iff x·f ∉ A(c') for ALL f: c → c' in C
~A (non-A, liberal complement): x ∈ ~A iff some element reaching x is not in A
x ∈ (~A)(c) iff x' ∉ A(c') for SOME f: c' → c and x' ∈ f⁻¹·x
Always: ¬A ≤ ~A (negation ⊆ complement)
| Operation | Formula | For Graphs |
|---|---|---|
| Boundary | ∂A = A ∧ ~A | Vertices in A connected to outside |
| Induced | ¬¬A | Same vertices, all edges between them |
| Expansion | ~¬A | A plus one layer outward |
| Contraction | ¬~A | A minus one layer inward |
A ∨ ¬A = ⊤ holds iff graph is discrete (no edges).
For connected graphs: excluded middle fails. This isn't a bug — it's topology speaking through logic.
The skill presents the neutral synthesis: rigorous definitions with practical Catlab code, acknowledging both the elegant mathematical structure and the implementation gaps.
@article{patterson2022categorical,
title={Categorical data structures for technical computing},
author={Patterson, Evan and Lynch, Owen and Fairbanks, James},
journal={Compositionality},
volume={4},
number={5},
year={2022},
doi={10.32408/compositionality-4-5}
}
GeoACSets.jl combines ACSets with geospatial capabilities:
Use morphisms for structural navigation, geometry for filtering.
| Operation | Complexity | When to Use |
|---|---|---|
| Morphism traversal | O(k) | Hierarchical containment |
| Spatial join | O(n log n) | Ad-hoc proximity queries |
# 4-level hierarchy: Region → District → Parcel → Building
@present SchSpatialCity(FreeSchema) begin
Region::Ob
District::Ob
Parcel::Ob
Building::Ob
district_of::Hom(District, Region)
parcel_of::Hom(Parcel, District)
building_on::Hom(Building, Parcel)
GeomType::AttrType
region_geom::Attr(Region, GeomType)
footprint::Attr(Building, GeomType)
end
@acset_type SpatialCity(SchSpatialCity,
index=[:district_of, :parcel_of, :building_on])
# Downward: O(depth) via incident queries
buildings_in_region(city, region_id)
# Upward: O(1) via subpart lookups
region_of_building(city, building_id)
# Combine spatial + morphism
nearby = spatial_filter(city, :Building, :footprint,
g -> LibGEOS.distance(g, query_point) < 100)
for b in nearby
district = traverse_up(city, b, :building_on, :parcel_of)
end
GeoACSets needs extension for foundation model integration:
@present SchOlmoEarthPatch(FreeSchema) begin
Patch::Ob # Variable-size spatial patch
Timestep::Ob # Monthly temporal unit
Modality::Ob # Sentinel-1/2, Landsat, Maps
Token::Ob # Encoded representation
View::Ob # For instance contrastive
patch_timestep::Hom(Patch, Timestep)
patch_modality::Hom(Patch, Modality)
token_patch::Hom(Token, Patch)
# Masking as structured decomposition
MaskedPatch::Ob
MaskConfig::Ob
masked_patch::Hom(MaskedPatch, Patch)
mask_state::Attr(MaskedPatch, MaskStateType) # encode/decode/both/none
end
# OlmoEarth masking creates:
# EncodeBag ← Apex (both) → DecodeBag
function create_masking_decomposition(patches, config_id)
encode_bag = filter(p -> mask_state(p) ∈ [:encode_only, :both], patches)
decode_bag = filter(p -> mask_state(p) ∈ [:decode_only, :both], patches)
apex = filter(p -> mask_state(p) == :both, patches)
(encode_bag, apex, decode_bag)
end
# Two views must agree on pooled representation
function verify_sheaf_condition(patches; threshold=0.99)
pooled1 = patches[view1, :pooled_repr]
pooled2 = patches[view2, :pooled_repr]
cosine_sim(pooled1, pooled2) >= threshold
end
Gay.jl uses a categorical label system on GitHub issues. These map directly to ACSet concepts:
| Label | Color | Description |
|---|---|---|
ternary:+ | #286e49 | Positive trit [+1] |
ternary:0 | #4a9235 | Zero trit [0] |
ternary:- | #28a628 | Negative trit [-1] |
| Label | Color | Description |
|---|---|---|
acset:rewriting | #5dda92 | ACSet local rewriting gadgets |
acset:adhesion | #d15252 | Structured decomposition adhesions |
| Label | Color | Description |
|---|---|---|
sheaf:descent | #97286e | Descent condition verification |
sheaf:covering | #282e69 | Covering sieve/condition |
sheaf:gluing | #28a289 | Gluing axiom / section construction |
sheaf:obstruction | #96a428 | Non-sheaf witness / descent failure |
| Label | Color | Description |
|---|---|---|
chromatic:spi | #37dc48 | Strong Parallelism Invariant |
chromatic:fingerprint | #59dc8a | XOR fingerprint composition |
chromatic:propagation | #93b7bd | Color propagation rules |
chromatic:split | #92b8c8 | gay_split() ancestry |
| Label | Color | Description |
|---|---|---|
spectral:fourier | #282c5c | FFT/DFT presheaf operations |
spectral:periodicity | #b24b60 | Periodic structure detection |
spectral:quasi | #6991dc | Quasi-sheaf / boundary cases |
spectral:threshold | #28bc3f | Threshold boundary analysis |
| Label | Color | Description |
|---|---|---|
coherence:pentagon | #f97316 | Mac Lane pentagon identity |
coherence:hexagon | #ef4444 | Mac Lane hexagon identity |
monoidal:symmetric | #a855f7 | Symmetric monoidal structure |
logic:separation | #6366f1 | Separation logic for ownership |
| Label | Color | Description |
|---|---|---|
health:composable | #10b981 | Health score ≥60, composable seed |
health:obstructed | #f43f5e | Health score <60, obstructed seed |
remediation:spectral | #22c55e | Spectral obstruction remediation |
remediation:mixing | #14b8a6 | Additional mixing rounds |
| Label | Color | Description |
|---|---|---|
scope:change | #b0dcb4 | Propagator fires on property change |
scope:geo | #36599a | Propagator fires on spatial overlap |
scope:tick | #9f9565 | Propagator fires on frame/timestep |
scope:click | #472835 | Propagator fires on explicit trigger |
Gay.jl implements topos-theoretic gamut classification:
# Truth values with distance semantics
struct GamutTruth
in_gamut::Bool
distance::Float64 # 0 = boundary, - = inside, + = outside
boundary_hue::Float64
end
# Characteristic morphism χ: Color → Ω
χ_srgb = characteristic_morphism(GaySRGBGamut(), GayRec2020Gamut())
truth = χ_srgb(RGB(0.5, 0.8, 0.3))
# => GamutTruth(true, -0.2, 120.0)
# Pullback recovers subobject (sub-C-set!)
in_srgb = gamut_pullback(χ_srgb, colors)
ACSet connection: Subobject classifier Ω in topos of C-sets = propositional logic from Blog IV.
Propagators form an operad with ACSet adhesions:
# Operadic composition
P(n) = {n-ary propagators: (source₁,...,sourceₙ, target) → target'}
# Example composition
p: (a,b) → c ∈ P(2)
q: (x) → a ∈ P(1)
r: (y,z) → b ∈ P(2)
γ(p; q, r): (x, y, z) → c ∈ P(3)
Colored operad: Types = Seed, Color, Sound, Contract
P(Seed → Color) ∘ P(Color → Sound) : P(Seed → Sound)
7 obstruction detectors map to C-set/sheaf failures:
| Detector | ACSet Interpretation |
|---|---|
spectral | FFT presheaf descent failure |
linear | LFSR complexity (non-randomness) |
gcd | Marsaglia GCD test |
birthday | Collision spacing |
cech | H^1 cohomology = gluing failure |
fingerprint | XOR collision = non-uniqueness |
coherence | Pentagon/hexagon = associativity failure |
# Analyze obstructions
report = analyze_obstructions(1069)
# Mine for obstructed seeds
bad_seeds = mine_obstructed_seeds(1:1000, 10)
# Remediate
better_seed = remediate_spectral(SPISeed(35))
H^1 measures "how far from being a sheaf":
# H^1 = 0 → proper sheaf (sections glue)
# H^1 ≠ 0 → obstruction class exists
function cech_h1_obstruction(seed, depth=7)
fingerprints = [xor_fingerprint(gay_split(seed, i)) for i in 1:depth]
# Check if local fingerprints glue globally
failures = count(i -> fingerprints[i] ⊻ fingerprints[i+1] ≠ expected[i], 1:depth-1)
failures > 0 # true = obstruction detected
end
Mac Lane's pentagon and hexagon for monoidal categories:
# Pentagon identity for 4-way associativity
# ((a ⊗ b) ⊗ c) ⊗ d must equal a ⊗ (b ⊗ (c ⊗ d))
# via ANY path through the pentagon
function verify_pentagon(split_fn, seed)
paths = enumerate_pentagon_paths(seed)
all(p1 ≈ p2 for (p1, p2) in pairs(paths))
end
# Hexagon identity for braiding
function verify_hexagon(split_fn, seed)
# σ_{a,b⊗c} = (1 ⊗ σ_{a,c}) ∘ (σ_{a,b} ⊗ 1)
left_path = braid_then_tensor(seed)
right_path = tensor_then_braid(seed)
left_path ≈ right_path
end
The canonical seed used across Gay.jl issues:
seed = 1069
trits = [+1, -1, -1, +1, +1, +1, +1] # 7-trit signature
# Properties:
# - Passes all spectral tests
# - Clean H^1 (no Čech obstructions)
# - Pentagon/hexagon coherent
# - health:composable (≥60 score)
Local rewriting rules colored by Gay.jl:
using AlgebraicRewriting, Gay
# Rule: merge two vertices
rule = @rule SchGraph begin
L = @acset begin v1::V; v2::V end
R = @acset begin v::V end
# L → R collapses v1, v2 → v
end
# Color the rewrite
seed = 1069
L_colors = Gay.palette(seed, nparts(L, :V))
R_colors = Gay.palette(seed, nparts(R, :V))
# Verify: rewrite preserves GF(3) trit sum
@assert gf3_conserved(L_colors) == gf3_conserved(R_colors)
From StructuredDecompositions.jl + Gay.jl:
# Adhesion = shared boundary between decomposition pieces
# Color adhesions to track gluing
struct ColoredAdhesion
left_piece::ACSet
right_piece::ACSet
adhesion::ACSet # shared sub-ACSet
color::String # Gay.jl deterministic color
end
function color_decomposition(decomp, seed)
[ColoredAdhesion(
piece.left, piece.right, piece.adhesion,
Gay.color_at(seed, i)
) for (i, piece) in enumerate(decomp.pieces)]
end
The ironic detachment comes from recognizing that:
xenomodernity
│
┌─────────┴─────────┐
│ │
ironic sincere
detachment engagement
│ │
└─────────┬─────────┘
│
C-sets as functors
(both ironic AND sincere)
just acset-demo # Run ACSet demonstration
just acset-graph # Create and visualize graph
just acset-symmetric # Symmetric graph example
just acset-gf3 # Check GF(3) conservation
ACSet-based edge growth with spectral constraints:
@present SchRamanujanGraph <: SchGraph begin
SpectralData::AttrType
lambda2::Attr(V, SpectralData) # Track λ₂ per growth step
end
function grow_edge_ramanujan!(G::ACSet, u, v)
"""
Add edge preserving Ramanujan property.
Uses Alon-Boppana bound: λ₂ ≥ 2√(d-1).
"""
d = degree(G)
bound = 2 * sqrt(d - 1)
# Tentatively add edge
add_part!(G, :E, src=u, tgt=v)
# Check spectral constraint
λ₂ = second_eigenvalue(adjacency_matrix(G))
if λ₂ > bound + 0.01 # Tolerance
# Rollback: remove edge
rem_part!(G, :E, nparts(G, :E))
return false
end
return true
end
@present SchNonBacktracking(FreeSchema) begin
V::Ob; E::Ob; DE::Ob # DE = directed edges
src::Hom(E,V); tgt::Hom(E,V)
forward::Hom(E, DE); backward::Hom(E, DE)
de_src::Hom(DE, V); de_tgt::Hom(DE, V)
# Non-backtracking constraint: head(e) = tail(f) ∧ e ≠ f⁻¹
nonbacktrack::Hom(DE, DE) # B matrix as morphism
end
# Ihara zeta via ACSet homomorphisms
function prime_cycles(G::ACSet, max_length)
cycles = []
for k in 1:max_length
if moebius(k) != 0 # Only squarefree lengths
push!(cycles, find_cycles(G, k))
end
end
return cycles
end
function alternating_centrality(G::ACSet)
"""
Centrality via Möbius-weighted path counts.
c(v) = Σ_{k} μ(k) × paths_k(v) / k
"""
n = nparts(G, :V)
A = adjacency_matrix(G)
c = zeros(n)
for k in 1:diameter(G)
μ_k = moebius(k)
if μ_k != 0
paths_k = diag(A^k)
c .+= μ_k .* paths_k ./ k
end
end
return c ./ sum(abs.(c))
end
Schema and attribute types known at compile time, enabling performance optimizations.
StructACSet{S, Ts, PT}
# S = TypeLevelSchema{Symbol} - schema at compile time
# Ts = Tuple of Julia types for attributes (e.g., Float64 for Weight)
# PT = PartsType strategy (IntParts or BitSetParts)
struct StructACSet{S, Ts, PT}
parts::NamedTuple # {:V => IntParts, :E => IntParts, ...}
subparts::NamedTuple # {:src => Column, :tgt => Column, :weight => Column, ...}
end
# Column types:
# - Homs: Vector{Int} mapping parts to parts
# - Attrs: Vector{Union{AttrVar,T}} for attribute values
@acset_type Graph(SchGraph,
index=[:src, :tgt], # Preimage cache: O(1) incident queries
unique_index=[:inv] # Injective cache: even faster
)
# Index types:
# - NoIndex: Linear scan O(n)
# - Index (StoredPreimageCache): O(1) average via hash
# - UniqueIndex (InjectiveCache): O(1) guaranteed, injective morphisms only
| Strategy | Type | Deletion | Use Case |
|---|---|---|---|
| IntParts | DenseParts | Pop-and-swap (renumbers) | Fast, compact storage |
| BitSetParts | MarkAsDeleted | Preserves IDs, requires gc!() | Stable references |
# IntParts (default): contiguous IDs 1..n
add_parts!(G, :V, 3) # IDs: 1, 2, 3
rem_part!(G, :V, 2) # ID 3 → 2, ID 2 gone
# BitSetParts: sparse IDs with gaps
rem_part!(G, :V, 2) # ID 2 marked deleted, ID 3 unchanged
gc!(G) # Compact: removes gaps
ramanujan-expander (-1) ⊗ acsets (0) ⊗ gay-mcp (+1) = 0 ✓ [Graph Coloring]
ramanujan-expander (-1) ⊗ acsets (0) ⊗ moebius-inversion (+1) = 0 ✓ [Edge Growth]
ihara-zeta (-1) ⊗ acsets (0) ⊗ moebius-inversion (+1) = 0 ✓ [Prime Cycles]
sheaf-cohomology (-1) ⊗ acsets (0) ⊗ gay-mcp (+1) = 0 ✓ [ACSet Navigation]