AFTD Auto-Formalizing Theoretical Domains

oriented_star_density

def

The homomorphism density of an oriented star with center c in a digraphon W is the integral over x in [0, 1] of (W^-(x))^(inDegree c) * (W^+(x))^(outDegree c).

Statement

noncomputable def oriented_star_density {V : Type*} [Fintype V]
    (D : Digraph V) [DecidableRel D.Adj] (c : V) (W : ℝ → ℝ → ℝ) : ℝ
Defined in
arXiv:2611.15027 Section 6.1
Verified
15 Nov 2026
Axioms
none listed
Built on 4
  • digraph_in_degreeThe in-degree of a vertex v in a finite directed graph D is the number of vertices u such that D.Adj u v.
  • digraphon_in_marginalThe in-degree marginal W-(x) of a digraphon W at x is the integral of W(y, x) over y in [0, 1].
  • digraphon_out_marginalThe out-degree marginal W+(x) of a digraphon W at x is the integral of W(x, y) over y in [0, 1].
  • digraph_out_degreeThe out-degree d⁺(v) of a vertex v in a finite directed graph D is the number of out-neighbors of v, that is, the cardinality of the set…
Used by 3
  • is_os_oriented_starAn oriented star with center c is oriented Sidorenko (OS) if for every digraphon W, its density in W is at least its density in (W + W^T)…
  • oriented_star_one_edge_os_and_oasIf an oriented star D has one edge (two vertices), then D is both OS and OAS.
  • is_oas_oriented_starAn oriented star with center c is oriented anti-Sidorenko (OAS) if for every digraphon W, its density in W is at most its density in (W +…

Read back from the Lean

Given a finite type V, a directed graph D on V with decidable adjacency relation, a vertex c ∈ V, and a two-variable function W : ℝ → ℝ → ℝ, oriented_star_density D c W is the real number defined by the Bochner integral over x ∈ [0, 1] of: (digraphon_in_marginal W x)^(digraph_in_degree D c) * (digraphon_out_marginal W x)^(digraph_out_degree D c).

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

/-- Homomorphism density of an oriented star with center c in a digraphon W. -/
noncomputable def oriented_star_density {V : Type*} [Fintype V]
    (D : Digraph V) [DecidableRel D.Adj] (c : V) (W : ℝ → ℝ → ℝ) : ℝ := ∫ x in Set.Icc (0 : ℝ) 1,
    (digraphon_in_marginal W x) ^ (digraph_in_degree D c) *
    (digraphon_out_marginal W x) ^ (digraph_out_degree D c)
See it in the graphDiscuss this resultChallenge it