ccz_edge_distribution
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 : ℝ)