Acyclic Partition Functions

construct_ap_space(lc::AbstractComplex; connected::Bool=true)

Construct the space of acyclic partitions of lc.

Starting from the partition of lc into singletons (Morse vector f(X), the finest possible acyclic partition), repeatedly merges pairs of blocks of an already-found acyclic partition into a single block, keeping only merges that preserve acyclicity (mvf_is_acyclic), until every pair of blocks at every level has been tried. This reaches every element of the poset AP(X) (see stratum_partition and stratum_adjacency for its Morse-vector stratification), ordered by atomic refinement (is_atomic_refinement).

If connected=true (the default), a merge is only attempted when the two blocks are topologically adjacent (lefschetz_neighbors), so only partitions built from connected multivectors are reached – this is AP^c(X), the sub-poset of practical interest for e.g. Forman-vector-field style examples, and is dramatically cheaper to enumerate. If connected=false, every pair of blocks is tried regardless of adjacency, reaching the full, unrestricted AP(X), including partitions with disconnected multivectors; this is needed whenever a question genuinely requires disconnected pieces (a weight-1 Morse-vector jump, for instance, is only guaranteed uniform when drawn from the unrestricted AP(X) – see stratum_adjacency). The unrestricted enumeration can be substantially larger than the connected one, and may not be tractable for complexes with more than a handful of cells; construct_ap_stratum targets a single Morse-vector stratum directly and can remain tractable well past that point.

Returns a Vector{Vector{Vector{Int}}}: each entry is one element of AP(X) (or AP^c(X)) as a multivector field in integer form (singletons omitted, matching the usual CellSubsets convention).

construct_ap_stratum(lc::AbstractComplex, target::Vector{Int}; connected::Bool=true)

Construct only the elements of AP(X) (or AP^c(X) if connected=true, the default) whose Morse vector equals target, without enumerating the rest of the poset.

Uses the same merge-based search as construct_ap_space, but prunes a branch the moment its current Morse vector fails to dominate target in every coordinate: refinement never decreases the Morse vector (delta = beta(A)+beta(B)-beta(C) >= 0 for any merge of two blocks A, B into C, by Lemma 3.3 of doc/morse-vector-strata.md – "Monotonicity... holds for all refinements, not only atomic ones"), so once some coordinate has dropped below target[k], no further merge can ever bring it back and the branch can safely be dropped. Nodes whose Morse vector matches target exactly are still expanded further, since additional Morse-vector- preserving (delta=0) merges can still produce further distinct partitions belonging to the same stratum.

Each accepted merge updates the running Morse vector incrementally from the two merged blocks' already-known Conley indices (beta(A)+beta(B) - beta(C), memoized in a shared cache keyed by block) rather than recomputing the whole partition's Morse vector from scratch at every node. This incremental update is only ever applied to blocks belonging to an already-mvf_is_acyclic-accepted partition – conley_index errors on a subset that is not locally closed, and a rejected merge candidate's merged block carries no such guarantee, so the acyclicity check always runs first.

Whether this is actually faster than calling construct_ap_space and filtering by Morse vector afterward is target-dependent, not automatic: target = beta(X) is a global lower bound on the Morse vector of every element of AP(X) (the "Extremes" property, Section 3.3), so pruning against it never triggers and this degenerates to the full enumeration with extra per-node overhead. For a genuinely intermediate target, however, most branches do get cut, and the saving can be large – e.g. for a 13-cell example where the connected AP^c(X) has 40232 elements, fixing an intermediate stratum of 537 elements takes on the order of a tenth of a second here versus several seconds for full enumeration plus filtering. The main intended use is targeting a single stratum of the unrestricted AP(X) on complexes where full unrestricted enumeration (construct_ap_space(lc; connected=false)) is no longer tractable at all.

Returns a Vector{Vector{Vector{Int}}}, in the same format as construct_ap_space.

convert_partition_mvf(sp::Set{Set{Int}})

Convert a set partition into a multivector field.

sp is a full partition of a complex's cells into blocks, including singleton blocks (the representation used internally by construct_ap_space and construct_ap_stratum). Returns the corresponding CellSubsets-style multivector field: singleton blocks are dropped (they are implicit critical cells) and every remaining block is returned as a sorted Vector{Int}.

convert_mvf_partition(lc::AbstractComplex, mvf::CellSubsets)

Convert a multivector field into a set partition.

The inverse of convert_partition_mvf: adds the implicit singleton blocks (every cell of lc not already covered by mvf) and returns the result as a Set{Set{Int}}, the full-partition representation used internally by construct_ap_space and construct_ap_stratum.

is_atomic_refinement(lc::AbstractComplex, mvf1::CellSubsets, mvf2::CellSubsets)

Determine whether mvf1 is an atomic refinement of mvf2, i.e. whether mvf1 and mvf2 are elements of AP(X) with mvf1 obtained from mvf2 by splitting exactly one block of mvf2 into two. Equivalently, mvf1 and mvf2 cover each other in the atomic-refinement order used throughout the construct_ap_space, atomic_distances, and stratum_adjacency functions.

atomic_distances(lc::AbstractComplex, ap::Vector{Vector{Vector{Int}}}; p::Int=99991)

Compute the atomic-refinement adjacency matrix of ap (typically the output of construct_ap_space).

Returns a sparse matrix A (in the ConleyDynamics sparse format, over the prime field p) with A[i,j] == 1 iff ap[i] is an atomic refinement of ap[j] (is_atomic_refinement(lc, ap[i], ap[j])). This is the expensive step of the pipeline (checking every pair of elements at adjacent lengths), and is what stratum_adjacency uses to determine coverage between Morse-vector strata.

is_connected_block(lc::AbstractComplex, block::Cells)

Whether block is connected as a subspace of lc – the "c" in AP^c(X).

This is a genuinely different question from block_rho's rho_0 and beta_0: those come from the restricted boundary operator on the block (Fact 1.1) and measure homological cancellation, which is 0 for any regular (non-critical) multivector regardless of whether it is topologically connected – e.g. a Forman pair {v,e} with v a face of e is connected as a subspace but has beta(V) = (0,0,...) because it is non-critical. Connectivity here instead means: is the comparability graph of block (edges wherever one cell is a direct face of another, both cells inside block) a single connected component. Reachability via direct face relations already captures full order-comparability, since any longer chain x < y < z decomposes into direct-face steps.

is_connected_partition(lc::AbstractComplex, mvf::CellSubsets)

Whether every explicit multivector of mvf is connected (is_connected_block); implicit singletons are always connected. This is exactly the membership test for AP^c(X), the sub-poset that construct_ap_space(lc; connected=true) enumerates directly.

is_closed_in_block(lc::AbstractComplex, A::Vector{Int}, blockset::Set{Int})

Whether A is closed in the block blockset (Theorem 2.1: A is closed in block C iff cl(A) cap C = A).

morse_vector(lc::AbstractComplex, mvf::CellSubsets)

Morse vector M(W) = sum_{V in W} beta(V) of a multivector field/partition mvf. Every non-critical block contributes 0, so this is just the sum of the Conley indices of the critical multivectors.

block_rho(lc::AbstractComplex, block::Cells)

The rank vector (rho_0(V),...,rho_n(V)) of a single locally closed multivector block, recovered from beta(V) and f(V) via Lemma 3.1: f(V) - beta(V) = sum_k rho_k(V) (e_k + e_{k-1}).

Uses beta(V) = conley_index(lc, block), which by Fact 1.1 coincides with the absolute homology of the restricted boundary operator for any locally closed V.

block_split_deltas(lc::AbstractComplex, block::Cells)

Enumerate every atomic split C = A ⊔ B of block with A closed in C (Theorem 2.1, Proposition 2.2), and return the achieved delta = beta(A) + beta(B) - beta(C) together with A and B for each (the split spectrum D({C}) of Corollary 2.3). Brute force over all subsets, so only intended for small blocks (length(block) <= 20).

split_spectrum(lc::AbstractComplex, block::Cells)

The set D({C}) of distinct delta vectors achievable by a single atomic split of block.

connected_split_deltas(lc::AbstractComplex, block::Cells)

Like block_split_deltas, but restricted to splits C = A ⊔ B with both A and B topologically connected (is_connected_block) – the deltas actually reachable by a single atomic refinement step while staying inside AP^c(X), as opposed to the unrestricted AP(X) of Theorem 5.1's existence statement.

stratum_partition(lc::AbstractComplex, ap::Vector{Vector{Vector{Int}}})

Group the enumerated acyclic partitions ap = construct_ap_space(lc) by their Morse vector. Returns Dict{Vector{Int},Vector{Int}} mapping M to the indices into ap with morse_vector(lc, ap[i]) == M.

stratum_jump_weight(delta::Vector{Int})

The weight |c| of the canonical decomposition delta = sum_k c_k (e_k+e_{k-1}).

stratum_adjacency(lc::AbstractComplex, ap::Vector{Vector{Vector{Int}}}; A=nothing)

For every pair of distinct strata M1 > M2 for which at least one element of AP_{M2} admits an atomic refinement into AP_{M1}, report the jump delta = M1-M2, its weight |c|, how many of AP_{M2}'s elements are covered from M1, and whether coverage is uniform.

A, if supplied, must be atomic_distances(lc, ap); otherwise it is computed internally (this is the expensive step, so pass it in if already available).

_rank_decomposition(d::Vector{Int})

Solve d_k = rho_k + rho_{k+1} for rho, given rho_0 = 0 and d indexed 1:n+1 for dimensions 0:n (Lemma 3.1's inversion). The same recursion also extracts the c_k in the canonical decomposition of a Morse-vector jump delta = sum c_k(e_k+e_{k-1}).

Internal helper, not exported.