01
The stream
Edges arrive and depart one at a time — insertions, deletions, insertions again. The graph never sleeps, and the matching must keep up without ever rebuilding from scratch.
STOC 2026 · arXiv:2605.00797Keep maximal matching
Keep maximal matching
maximal, at speed.
Axiom is a pure-Python implementation of the Chuzhoy–Khanna–Song algorithm — maintaining a maximal matching under online edge insertions and deletions inÕ(n½+o(1)) amortised time.
struct axiom · pure python · zero deps · mypy strict
click two nodes to toggle an edge · click an edge to delete it
Maximal ✓n —|E| —|M*| —repair —0000 updates
Õ(n^1/2+o(1))
amortised update time
tiered mode · Theorem 1.1
Θ(log n)
hierarchy levels
k-level recursive partition
7
invariants verified
checked after every update
0
runtime dependencies
pure Python · stdlib only
The problemGraphs change every second.
Graphs change every second.
The answer is always current.
Fully dynamic maximal matching is the workhorse at the heart of scheduling, real-time routing, and large-graph approximation. The hard part isn't finding a matching — it's that the graph refuses to stay still.
02
The invariant
A maximal matching stays an l̶ocal proof of coverage: every edge touches at least one matched vertex. Recover it instantly, deterministically, after every single update.
03
The cost
The z-subgraph system localises damage so each update costs only Õ(n^1/2+o(1)) amortised work — the fastest known deterministic bound for this problem.
CapabilitiesEngineered to hold one promise:
Engineered to hold one promise:
maximal, always.
Every subsystem earns its place. Nothing is stubbed, nothing is decor — each piece of the paper's construction is implemented, maintained, and provably checked.
Two operating modes
basic runs the single-level Õ(n^2/3) algorithm; tiered runs the n^1/2+o(1) k-level recursion with k ≈ ½ log n. Swap policies without touching your code.
z-subgraph system
The full (A, B, U) partition, S = A ∪ B saturation, Λ(u) and L(a) index lists, and all seven invariants from Section 2 of the paper — implemented, not stubbed.
Deterministic colouring
Vizing's alternating-path recolouring delivers (Δ+1)-colours, and a degree-ordered greedy fast-path partitions M into colour classes for rematch dispatch.
Invariant checks
Independent read-only validators prove maximality, every z-system property, and the multi-level (I3) bound at any moment. Call them from tests or debug scripts.
Augmenting-path API
augment(), try_augment(), and flip() are first-class public methods — no name-mangled privates. Drive the matching machinery directly from your own code.
Empirical ledger
Explicit counters track rebuilds, rematch scan sizes, stale cleanups, and greedy fallbacks — a precise account of where every update spends its time.
deterministicpure pythonzero depsmypy · stricttyped protocolsseeded ≈ reproducible
Operating modesTwo engines.
Two engines.
One contract.
Pick the recursion depth that fits your graph. Both modes expose the same strict, typed API — the difference is only in how deeply they arm against the update stream.
Basic
single-level · deterministicÕ(n^2/3)amortised per update
- z = ⌈n^2/3⌉ saturation threshold
- phase length r = ⌈n^4/3⌉
- subphase length r / z
- ideal for mid-size graphs & teaching
strategy =
policy=Basic()Tiered
multi-level · k = Θ(log n)n^1/2+o(1)amortised per update
- z₁ = n, zᵢ = zᵢ₋₁ / 2 recursive levels
- k = ⌈log₂ √n⌉ hierarchy depth
- level-k threshold z_k ≈ √n
- Invariant (I3) enforced after every update
strategy =
policy=Tiered()Prefer strings for legacy code? Matcher(n=100, mode="basic") andMatcher(n=100, mode="tiered") keep working — passing a policy is the recommended path for new code.
Get movingThree walls in.
Three walls in.
You're running.
The whole surface is a handful of well-typed calls. Insert. Delete. Ask. Invariant checkers, augmenting paths, and an amortised ledger are all a first-class import away.
- Public
augment/flipAPI — no name mangling - Standalone invariant validators for tests & debugging
- Deterministic, seeded, replayable update streams
pip install git+https://github.com/sachncs/axiom.git$ python demo.py
from axiom import Matcher
algo = Matcher(n=100, mode="tiered")
algo.insert(0, 1) # edge arrives
algo.insert(2, 3)
algo.delete(1, 0) # edge leaves
assert algo.maximal() # still maximal — instantly
print(algo.matching()) # {(2, 3)}
print(algo.size()) # 1
print(algo.stats()) # amortised ledger$ axiom --n 20 --mode basic --updates 200 --seed 42
=== Axiom Demo: n=20, mode=basic, updates=200 ===
Completed 200 updates in 0.001s
Final edges: 12
Matching size: 8
Maximal: True# Strobes of work land on a dark chart —
# matching size stays maximal through every
# update, while the ledger explains the cost.
n=200 · updates=5000 · mode=tiered ───■── 6.2k upd/s
rebuilds 827
rematch scans 12,913
stale cleanups —·
greedy fallbacks 31maximal ✓zero runtime depspython 3.10 – 3.13
Ready for the streamYour matching deserves
Your matching deserves
deterministic excellence.
One import, zero dependencies, every invariant verified. Clone the repo, run the demo, and break it — the checkers will thank you.
pip install git+https://github.com/sachncs/axiom.git