Sensitivity graph validation on exact-sized forbidden subsets
DefinitionSensitivityGraphLocalLet a raw input consist of a finite directed graph, binary edge labels, its regular degree, ordinary and source cutoffs, and a finite list of tolerance cutoffs. This interface keeps the original vertex, cutoff, tournament, and regularity conditions. It replaces the three all-size labeling checks by forbidden configurations at exactly the corresponding cutoff size.
For an ordinary cutoff, exclude a coherent coloring on every subset of that size. For tolerance , exclude a coloring on a subset of the -cutoff size in which every vertex has at most outgoing label disagreements. For the source cutoff, exclude a zero-defect coloring on a subset of that size that has a vertex pointing to every other vertex.
The finite sets of candidates are generated with powersetCard. Colorings still range over the full vertex set. The numerical profile recurrence, finite recipe alphabet, dominance pruning, and height test are copied without change from the original checker. The new checker accepts precisely when its local graph checks hold and
holds for a retained profile at depth , where is the vertex count. Equivalence to the original checker is a separate theorem. No successful input or practical runtime bound is asserted.
import Definitions.Def_SensitivityGraphCheck
/-! Numerical search on raw graph parameters, independent of validity proofs. -/
set_option autoImplicit false
set_option synthInstance.maxSize 256
namespace SensitivityGraphLocal
open SensitivityProfileCycle SensitivityProfileSearch SensitivityVariableWord
open SensitivityGraphCheck
def rawStep {n : ℕ} (D : RawData) (C : Recipe n) (P : Profile n) : Profile n :=
⟨envelope (rawZeroSourceCombined D.vertices D.ordinaryCutoff
(extendCutoffs D.cutoffs) D.sourceCutoff C P.zero P.one),
envelope (rawOne D.degree C P.zero P.one)⟩
def rawExpand {n : ℕ} (D : RawData) (s : List (Profile n)) : List (Profile n) :=
s.flatMap fun P => (SensitivityVariableFrontier.alphabet D.toleranceCount n).map
fun C => rawStep D C.recipe P
def rawFrontier (D : RawData) (n : ℕ) : ℕ → List (Profile n)
| 0 => [normalize (unitProfile n)]
| k+1 => FiniteDominance.prune SensitivityVariableFrontier.Below
(rawExpand D (rawFrontier D n k))
def rawSucceeds (D : RawData) (n k : ℕ) : Bool :=
(rawFrontier D n k).any fun P => decide (height P ^ 43 < D.vertices ^ (20*k))
end SensitivityGraphLocal
namespace SensitivityGraphLocal
open SensitivityGraphCheck SensitivityProfileCycle
/-- Graph validation restricted to the first forbidden cardinality in each bound. -/
def LocalValid (D : RawData) : Prop :=
1 < D.vertices ∧
4 ≤ D.ordinaryCutoff ∧
4 ≤ D.sourceCutoff ∧
extendCutoffs D.cutoffs 0 = D.ordinaryCutoff ∧
(∀ i, ¬ D.adj i i = true) ∧
(∀ i j, i ≠ j → (D.adj i j = true ↔ ¬ D.adj j i = true)) ∧
(∀ i, (Finset.univ.filter (fun j => D.adj i j = true)).card = D.degree) ∧
(∀ I ∈ (Finset.univ : Finset (Fin D.vertices)).powersetCard D.ordinaryCutoff,
∀ colors : Fin D.vertices → Fin 2,
(∀ i ∈ I, ∀ j ∈ I, D.adj i j = true → D.label i j = colors j) → False) ∧
(∀ q : Fin D.toleranceCount,
∀ I ∈ (Finset.univ : Finset (Fin D.vertices)).powersetCard (D.cutoffs q),
∀ colors : Fin D.vertices → Fin 2,
(∀ i ∈ I,
(I.filter (fun j => D.adj i j = true ∧ D.label i j ≠ colors j)).card ≤ q.val) →
False) ∧
(∀ I ∈ (Finset.univ : Finset (Fin D.vertices)).powersetCard D.sourceCutoff,
∀ colors : Fin D.vertices → Fin 2,
(∃ s ∈ I, ∀ j ∈ I, j ≠ s → D.adj s j = true) →
(∀ i ∈ I,
(I.filter (fun j => D.adj i j = true ∧ D.label i j ≠ colors j)).card ≤ 0) →
False)
instance (D : RawData) : Decidable (LocalValid D) := by
unfold LocalValid
repeat' refine @instDecidableAnd _ _ ?_ ?_
all_goals infer_instance
/-- A data-only search guarded by exact-cardinality graph checks. -/
def succeeds (D : RawData) (n k : ℕ) : Bool :=
if LocalValid D then rawSucceeds D n k else false
end SensitivityGraphLocal