AFTD Auto-Formalizing Theoretical Domains

ccz_edge_distribution

deforiginal

For a simple graph G on a finite type V with decidable equality and decidable adjacency, and an edge subset F, ccz_edge_distribution G F is the probability that the induced edge set of a uniformly random vertex subset equals F.

Statement

noncomputable def ccz_edge_distribution {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset (Sym2 V)) : ℝ
Related work
arXiv:2610.01024
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • ccz_induced_edgesFor a simple graph G on a finite type V and a vertex subset S, ccz_induced_edges G S is the set of edges of G both of whose endpoints lie…
Used by 1
  • ccz_renyi_entropyFor a real order α and a simple graph G on a finite type V, ccz_renyi_entropy α G is the order-α Rényi entropy of the CCZ induced-edge…

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite set F of unordered pairs of vertices (Sym2 V), ccz_edge_distribution G F is the real number defined as the number of subsets S : Finset V such that the induced edge set of G on S (ccz_induced_edges G S) equals F, divided by 2 ^ |V|. In other words, it is the fraction of subsets S ⊆ V whose induced subgraph in G has edge set F (the probability under the uniform distribution on subsets of V).

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 probability distribution of induced edge sets under a uniform random vertex subset of G. -/
noncomputable def ccz_edge_distribution {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset (Sym2 V)) : ℝ :=
  ((Finset.univ.filter (fun S : Finset V => ccz_induced_edges G S = F)).card : ℝ) /
    (2 ^ Fintype.card V : ℝ)
See it in the graphDiscuss this resultChallenge it