Documentation

HexGraphIso.Nauty.Invariant.Stabilize

theorem Hex.GraphIso.Nauty.cellsPerm_symm {ptn : Array Nat} {level : Nat} {lab1 lab2 : Array Nat} (h : cellsPerm ptn level lab1 lab2) :
cellsPerm ptn level lab2 lab1

Cell-contents equivalence is symmetric.

theorem Hex.GraphIso.Nauty.refine_reachAt {n : Nat} {ctx : Ctx n} {ptnN labN : Array Nat} {levN : Nat} {lab ptn : Array Nat} {level : Nat} {active : VSet n} {numcells : Nat} (hreach : cellsPerm ptnN levN labN lab) (hnn : n ptn.size) (hszN : ptnN.size = ptn.size) (hlsz : lab.size = ptn.size) (hend : ptn[ptn.size - 1]! level) (hendN : ptnN[ptnN.size - 1]! levN) (hcoarse : ∀ (q : Nat), ptnN[q]! levNptn[q]! level) :
cellsPerm ptnN levN labN (refine ctx level lab ptn active numcells).lab

refine preserves reachability from an ancestor node's state: it permutes labels within cells of its own finer partition, and the ancestor's boundaries persist, so cell-content equivalence coarsens and composes. The node-relative form of refine_cellsReach.

theorem Hex.GraphIso.Nauty.breakout_reachAt {n : Nat} {ptnN labN : Array Nat} {levN : Nat} {lab ptn : Array Nat} {level tc len o : Nat} (hreach : cellsPerm ptnN levN labN lab) (hcell : IsCell ptn level tc len) (hsize : tc + len ptn.size) (hszN : ptnN.size = ptn.size) (hlsz : lab.size = ptn.size) (ho : o < len) (hend : ptn[ptn.size - 1]! level) (hendN : ptnN[ptnN.size - 1]! levN) (hcoarse : ∀ (q : Nat), ptnN[q]! levNptn[q]! level) :
cellsPerm ptnN levN labN (breakout n lab ptn (level + 1) tc lab[tc + o]!).fst

breakout preserves reachability from an ancestor node's state: individualization permutes within one cell of the current partition, which refines the ancestor's. The node-relative form of breakout_cellsReach.

theorem Hex.GraphIso.Nauty.cellStab_of_scatter {n : Nat} {ptnN labN lab₁ lab₂ γ : Array Nat} {levN : Nat} (hsp : ptnN.size = n) (hsN : labN.size = n) (hs1 : lab₁.size = n) (hendN : ptnN[ptnN.size - 1]! levN) (h1 : cellsPerm ptnN levN labN lab₁) (h2 : cellsPerm ptnN levN labN lab₂) (hsc : ∀ (i : Nat), i < nγ[lab₁[i]!]! = lab₂[i]!) :
CellStab ptnN levN labN γ

A scatter joining two labellings reachable from a node stabilizes the node's cells: on every cell the scatter carries the first labelling's contents to the second's, and both agree with the node's own contents up to permutation, so the node labelling mapped through the scatter is cell-wise a permutation of itself. This is how an admitted generator (the scatter of a leaf labelling over firstlab or canonlab) satisfies the CellStab hypothesis of childKey_of_orbPruned at every node above both leaves.

theorem Hex.GraphIso.Nauty.cellStab_refine {n : Nat} {ctx : Ctx n} {level : Nat} {lab ptn γ : Array Nat} {active : VSet n} {numcells : Nat} (hstab : CellStab ptn level lab γ) (hgsz : ctx.g.size = n) (hca : checkAutom ctx.g γ = true) (hsl : lab.size = n) (hlab : LabOk lab n) (hsp : ptn.size = n) (hend : ptn[ptn.size - 1]! level) (hstarts : ∀ (v : Nat), active.mem v = truev = 0 ptn[v - 1]! level) :
CellStab (refine ctx level lab ptn active numcells).ptn level (refine ctx level lab ptn active numcells).lab γ

A checked automorphism stabilizing a node's cells still stabilizes them after refinement: refine depends on the labelling only through cell contents (refine_perm) and commutes with the automorphism's renaming (refine_map), and the two transports meet at the refined state. The descent-propagation clause of the stabilization invariant.

theorem Hex.GraphIso.Nauty.cellStab_breakout {n : Nat} {ptn lab γ : Array Nat} {level tc len o : Nat} (hstab : CellStab ptn level lab γ) (hcell : IsCell ptn level tc len) (hsize : tc + len ptn.size) (hlsz : lab.size = ptn.size) (ho : o < len) (hlen2 : 2 len) (hend : ptn[ptn.size - 1]! level) (hvals : ∀ (q : Nat), ptn[q]! level + 1) (hfix : γ[lab[tc + o]!]! = lab[tc + o]!) :
CellStab (breakout n lab ptn (level + 1) tc lab[tc + o]!).snd.fst (level + 1) (breakout n lab ptn (level + 1) tc lab[tc + o]!).fst γ

A cell-stabilizing map fixing the individualized vertex still stabilizes the cells after individualization: the singleton is fixed outright, the remainder cell's stability follows from the target cell's by head cancellation, and every other cell is untouched. The individualization arm of descent propagation, paired with cellStab_refine.