AFTD Auto-Formalizing Theoretical Domains

graph_defect

def

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₂)}
See it in the graphDiscuss this resultChallenge it