is_os_oriented_star
def
An 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) / 2.
Statement
def is_os_oriented_star {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (c : V) : Prop
- Defined in
- arXiv:2611.15027 Definition 1
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 3
- oriented_star_densityThe 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) *…
- digraphon_symmetrizationGiven a function W : ℝ → ℝ → ℝ, its symmetrization digraphon_symmetrization W is the function fun x y => (W x y + W y x) / 2.
- is_digraphonA function W : ℝ → ℝ → ℝ is a digraphon if for all x, y ∈ [0, 1] we have 0 ≤ W x y ∧ W x y ≤ 1, and the uncurried function…
- Used by 1
- oriented_star_one_edge_os_and_oasIf an oriented star D has one edge (two vertices), then D is both OS and OAS.
Read back from the Lean
For a finite type V, a directed graph D : Digraph V with decidable adjacency, and a vertex c : V, is_os_oriented_star D c is the proposition that for every function W : ℝ → ℝ → ℝ, if W is a digraphon (meaning 0 ≤ W x y ≤ 1 for all x, y ∈ [0, 1] and (x, y) ↦ W x y is measurable), then the oriented star density of (D, c) in the symmetrization of W is less than or equal to the oriented star density of (D, c) in W.
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
/-- An oriented star is oriented Sidorenko (OS) if its density in any digraphon is at least its density in the symmetrized digraphon. -/ def is_os_oriented_star {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (c : V) : Prop := ∀ W : ℝ → ℝ → ℝ, is_digraphon W → oriented_star_density D c (digraphon_symmetrization W) ≤ oriented_star_density D c W