petrial_nullity_poly_disjoint_finset_union
theoremverified
If disjoint finite vertex sets have no edges between them, the nullity polynomial on their union is the product of the nullity polynomials induced on the two sets.
Statement
theorem petrial_nullity_poly_disjoint_finset_union {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s t : Finset V) (hdisj : Disjoint s t) (hcut : ∀ a ∈ s, ∀ b ∈ t, ¬ G.Adj a b) : petrial_nullity_poly (G.induce ((s ∪ t : Finset V) : Set V)) = petrial_nullity_poly (G.induce (s : Set V)) * petrial_nullity_poly (G.induce (t : Set V))
- Source
- Component factorization for the OP-1239 candidate.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- petrial_nullity_polyThe nullity generating polynomial of a finite graph G on V: the sum over all vertex subsets F of w raised to the nullity of the partial…
- petrial_nullity_poly_mul_of_cutIf no edge of G joins a vertex of s to a vertex outside s, then the nullity generating polynomial of G is the product of the nullity…
- petrial_nullity_poly_induce_induceThe nullity polynomial obtained by inducing on s and then on vertices in t equals the polynomial of the graph induced on the intersection…
- petrial_nullity_poly_isoIsomorphic finite simple graphs have the same partial Petrial nullity generating polynomial.
Lean source view module on GitHub
set_option maxRecDepth 10000 set_option maxHeartbeats 0 theorem petrial_nullity_poly_disjoint_finset_union {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s t : Finset V) (hdisj : Disjoint s t) (hcut : ∀ a ∈ s, ∀ b ∈ t, ¬ G.Adj a b) : petrial_nullity_poly (G.induce ((s ∪ t : Finset V) : Set V)) = petrial_nullity_poly (G.induce (s : Set V)) * petrial_nullity_poly (G.induce (t : Set V)) := by classical let S : Set V := ((s ∪ t : Finset V) : Set V) let A : Set S := {x | (x : V) ∈ s} have hc : ∀ a b : S, a ∈ A → b ∉ A → ¬ (G.induce S).Adj a b := by intro a b ha hb hadj have hbs : (b : V) ∉ s := hb have hbt : (b : V) ∈ t := by rcases Finset.mem_union.mp b.property with hs | ht · exact (hbs hs).elim · exact ht exact hcut a.1 ha b.1 hbt hadj let e1 : ((G.induce S).induce A) ≃g (G.induce (s : Set V)) := { toEquiv := { toFun := fun x => ⟨x.1.1, x.2⟩ invFun := fun x => ⟨⟨x.1, Finset.mem_union_left t x.2⟩, x.2⟩ left_inv := by intro x; apply Subtype.ext; apply Subtype.ext; rfl right_inv := by intro x; apply Subtype.ext; rfl } map_rel_iff' := by rfl } let e2 : ((G.induce S).induce Aᶜ) ≃g (G.induce (t : Set V)) := { toEquiv := { toFun := fun x => ⟨x.1.1, by have hn : (x.1 : V) ∉ s := x.2 rcases Finset.mem_union.mp x.1.2 with hs | ht · exact (hn hs).elim · exact ht⟩ invFun := fun x => ⟨⟨x.1, Finset.mem_union_right s x.2⟩, by change (x.1 : V) ∉ s intro hs exact (Finset.disjoint_left.mp hdisj) hs x.2⟩ left_inv := by intro x; apply Subtype.ext; apply Subtype.ext; rfl right_inv := by intro x; apply Subtype.ext; rfl } map_rel_iff' := by rfl } have h := petrial_nullity_poly_mul_of_cut (G.induce S) A hc rw [petrial_nullity_poly_iso _ _ e1, petrial_nullity_poly_iso _ _ e2] at h exact h