graph_defect
Let G be a graph on a finite vertex type α and let t be a natural number. The defect def_t(G) is the least nonnegative integer d such that every Z_t-labeling of the complete graph on 2|α| vertices either has the property that every copy of G has a vertex-disjoint copy of the same weight, or contains two copies of G of different weights on some vertex subset of size at most |α| + d.
Statement
noncomputable def graph_defect {α : Type*} [Fintype α] (G : SimpleGraph α) (t : ℕ) : ℕ
- Defined in
- arXiv:2611.14160 Definition 3.6
- Verified
- 12 Nov 2026
- Axioms
- none listed
Read back from the Lean
graph_defect {α : Type*} [Fintype α] (G : SimpleGraph α) (t : ℕ) : ℕ is defined as the infimum (sInf in ℕ) of the set of all natural numbers d such that:
For every edge labeling C of the complete graph on vertex set Fin (2 * Fintype.card α) with labels in ZMod t, at least one of the following two conditions holds:
1. For every copy f₁ of G in the complete graph ⊤ on Fin (2 * Fintype.card α), there exists a copy f₂ of G in ⊤ on Fin (2 * Fintype.card α) such that the vertex ranges of f₁ and f₂ are disjoint (Disjoint (Set.range f₁) (Set.range f₂)) and their weights under C are equal (copyWeight C f₁ = copyWeight C f₂).
2. There exists a vertex subset U : Finset (Fin (2 * Fintype.card α)) with cardinality at most Fintype.card α + d such that there exist two copies f₁, f₂ of G in ⊤ on Fin (2 * Fintype.card α) whose vertices are both contained in U (∀ v : α, f₁ v ∈ U and ∀ v : α, f₂ v ∈ U) and whose weights under C are distinct (copyWeight C f₁ ≠ copyWeight C f₂).
Here, the weight copyWeight C f of a copy f under labeling C is defined as the sum in ZMod t over all edges e : G.edgeSet of C (f.mapEdgeSet e).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The defect def_t(G) of a graph G on n vertices is the least nonnegative integer d such that every Z_t-labeling of K_{2n} either has a vertex-disjoint copy of the same weight for every copy of G, or some set of at most n+d vertices contains two copies of G with different weights. -/ noncomputable def graph_defect {α : Type*} [Fintype α] (G : SimpleGraph α) (t : ℕ) : ℕ := sInf {d : ℕ | let copyWeight (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t)) (f : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))) : ZMod t := open Classical in ∑ e : G.edgeSet, C (f.mapEdgeSet e) ∀ (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t)), (∀ (f₁ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))), ∃ (f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))), Disjoint (Set.range f₁) (Set.range f₂) ∧ copyWeight C f₁ = copyWeight C f₂) ∨ (∃ (U : Finset (Fin (2 * Fintype.card α))), U.card ≤ Fintype.card α + d ∧ ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))), (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧ copyWeight C f₁ ≠ copyWeight C f₂)}