AFTD Auto-Formalizing Theoretical Domains

is_fractional_clique_cover

def

A fractional K_r-cover of a graph G is an edge weighting w : Sym2 V → ℚ taking values in [0, 1] on edges of G such that for every r-clique Q in G, the sum of weights of edges in Q is at least 1.

Statement

def is_fractional_clique_cover {V : Type*} [DecidableEq V] (G : SimpleGraph V)
    (w : Sym2 V → ℚ) (r : ℕ) : Prop
Defined in
arXiv:2610.41371 Def. 2.2
Verified
07 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a type V with decidable equality, a simple graph G on V, an edge-weight function w : Sym2 V → ℚ, and a natural number r, is_fractional_clique_cover G w r asserts that both of the following hold: 1. For every edge e in G.edgeSet, 0 ≤ w e ∧ w e ≤ 1. 2. For every finite subset Q : Finset V, if Q is an r-clique of G (i.e., G.IsNClique r Q), then the sum of w e over all unordered pairs e = s(u, v) formed by distinct elements u, v ∈ Q (the image under (u, v) ↦ s(u, v) of Q.offDiag) is greater than or equal to 1.

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

/-- Definition of a fractional K_r-cover of a graph G. -/
def is_fractional_clique_cover {V : Type*} [DecidableEq V] (G : SimpleGraph V)
    (w : Sym2 V → ℚ) (r : ℕ) : Prop :=
  (∀ e ∈ G.edgeSet, 0 ≤ w e ∧ w e ≤ 1) ∧
  ∀ (Q : Finset V), G.IsNClique r Q →
    1 ≤ ∑ e ∈ Q.offDiag.image (fun p => s(p.1, p.2)), w e
See it in the graphDiscuss this resultChallenge it