AFTD Auto-Formalizing Theoretical Domains

oriented_star_one_edge_os_and_oas

theoremverifiedformalization

If an oriented star D has one edge (two vertices), then D is both OS and OAS.

Statement

theorem oriented_star_one_edge_os_and_oas
    {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (c : V)
    (hstar : is_oriented_star D c) (hcard : Fintype.card V = 2) :
    is_os_oriented_star D c ∧ is_oas_oriented_star D c
Formalizes
arXiv:2611.15027 Theorem 1.9 (1)
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • is_oriented_starA directed graph D is an oriented star with center c if it is loopless, asymmetric, every edge has c as an endpoint, and every other…
  • 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)…
  • 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 +…
  • 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…
  • 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].
  • 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_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…
  • 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) *…

Read back from the Lean

Let $V$ be a finite type, $D$ a directed graph on $V$ with decidable adjacency, and $c \in V$ a vertex. Suppose that $D$ is an oriented star centered at $c$ (meaning $D$ has no self-loops, every directed edge is incident to $c$, $D$ has no 2-cycles, and every vertex $u \neq c$ is adjacent to or from $c$) and that the cardinality of $V$ is 2. Then $(D, c)$ is both an OS-oriented star and an OAS-oriented star, meaning that for every digraphon $W$: 1. The oriented star density of $(D, c)$ in the symmetrization of $W$ is less than or equal to that in $W$, and 2. The oriented star density of $(D, c)$ in $W$ is less than or equal to that in the symmetrization of $W$ (hence the density in $W$ equals the density in the symmetrized digraphon).

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

open MeasureTheory

lemma oriented_star_one_edge_os_and_oas_integrable (W : ℝ → ℝ → ℝ) (hW : is_digraphon W) :
    Integrable (fun z : ℝ × ℝ => W z.1 z.2)
      ((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) := by
  have : IsFiniteMeasure ((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) :=
    inferInstance
  apply Integrable.of_bound (hW.2.aestronglyMeasurable) 1
  rw [Measure.prod_restrict]
  have hmeas : MeasurableSet (Set.Icc (0:ℝ) 1 ×ˢ Set.Icc (0:ℝ) 1) :=
    measurableSet_Icc.prod measurableSet_Icc
  apply ae_restrict_of_forall_mem hmeas
  rintro ⟨x, y⟩ ⟨hx, hy⟩
  dsimp
  have := hW.1 x y hx hy
  rw [abs_le]
  exact ⟨by linarith [this.1], this.2⟩

lemma oriented_star_one_edge_os_and_oas_symm_in (W : ℝ → ℝ → ℝ) (hW : is_digraphon W) :
    (∫ x in Set.Icc (0:ℝ) 1, digraphon_in_marginal (digraphon_symmetrization W) x) =
      ∫ x in Set.Icc (0:ℝ) 1, digraphon_in_marginal W x := by
  dsimp [digraphon_in_marginal, digraphon_symmetrization]
  have h1 : Integrable (fun z : ℝ × ℝ => W z.1 z.2)
      ((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) :=
    oriented_star_one_edge_os_and_oas_integrable W hW
  have h2 : Integrable (fun z : ℝ × ℝ => W z.2 z.1)
      ((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) :=
    h1.swap
  have h_add : Integrable (fun z : ℝ × ℝ => (W z.2 z.1 + W z.1 z.2) / 2)
      ((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) :=
    (h2.add h1).div_const 2
  rw [integral_integral (f := fun x y => (W y x + W x y) / 2) h_add]
  rw [integral_integral (f := fun x y => W y x) h2]
  have eq_swap : ∫ z, W z.2 z.1 ∂((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) =
      ∫ z, W z.1 z.2 ∂((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))) :=
    integral_prod_swap (Function.uncurry W)
  have h_lin : (∫ z, (W z.2 z.1 + W z.1 z.2) / 2 ∂((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1)))) =
      ((∫ z, W z.2 z.1 ∂((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1)))) +
       (∫ z, W z.1 z.2 ∂((volume.restrict (Set.Icc (0:ℝ) 1)).prod (volume.restrict (Set.Icc (0:ℝ) 1))))) / 2 := by
    rw [integral_div, integral_add h2 h1]
  rw [h_lin, eq_swap]
  ring

lemma oriented_star_one_edge_os_and_oas_symm_out (W : ℝ → ℝ → ℝ) (hW : is_digraphon W) :
    (∫ x in Set.Icc (0:ℝ) 1, digraphon_out_marginal (digraphon_symmetrization W) x) =
      ∫ x in Set.Icc (0:ℝ) 1, digraphon_out_marginal W x := by
  have h_symm : digraphon_out_marginal (digraphon_symmetrization W) =
                digraphon_in_marginal (digraphon_symmetrization W) := by
    ext x
    dsimp [digraphon_out_marginal, digraphon_in_marginal, digraphon_symmetrization]
    congr 1 with y
    ring
  rw [h_symm, oriented_star_one_edge_os_and_oas_symm_in W hW]
  dsimp [digraphon_in_marginal, digraphon_out_marginal]
  have hint := oriented_star_one_edge_os_and_oas_integrable W hW
  exact (integral_integral_swap hint).symm

lemma oriented_star_one_edge_os_and_oas_degrees
    {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (c : V)
    (hstar : is_oriented_star D c) (hcard : Fintype.card V = 2) :
    (digraph_in_degree D c = 1 ∧ digraph_out_degree D c = 0) ∨
    (digraph_in_degree D c = 0 ∧ digraph_out_degree D c = 1) := by
  classical
  have h_univ : (Finset.univ : Finset V).card = 2 := hcard
  have hc : c ∈ (Finset.univ : Finset V) := Finset.mem_univ c
  have h_erase : ((Finset.univ : Finset V).erase c).card = 1 := by
    rw [Finset.card_erase_of_mem hc, h_univ]
  obtain ⟨v, hv⟩ := Finset.card_eq_one.mp h_erase
  have hvc : v ≠ c := by
    intro h
    have hmem : v ∈ (Finset.univ : Finset V).erase c := by
      rw [hv]
      exact Finset.mem_singleton_self v
    rw [Finset.mem_erase] at hmem
    exact hmem.1 h
  have h_all : ∀ u : V, u = c ∨ u = v := by
    intro u
    by_cases h : u = c
    · left; exact h
    · right
      have : u ∈ (Finset.univ : Finset V).erase c := Finset.mem_erase.mpr ⟨h, Finset.mem_univ u⟩
      rw [hv] at this
      exact Finset.mem_singleton.mp this
  have h_loop := hstar.1
  have h_star_edge := hstar.2.2.2 v hvc
  have h_asymm := hstar.2.2.1
  dsimp [digraph_in_degree, digraph_out_degree]
  cases h_star_edge with
  | inl hcv =>
    have hnvc : ¬ D.Adj v c := h_asymm c v hcv
    right
    constructor
    · have : Finset.filter (fun u => D.Adj u c) Finset.univ = ∅ := by
        rw [Finset.filter_eq_empty_iff]
        intro u _
        rcases h_all u with rfl | rfl
        · exact h_loop u
        · exact hnvc
      rw [this, Finset.card_empty]
    · have : Finset.filter (D.Adj c) Finset.univ = {v} := by
        ext u
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
        constructor
        · intro hu
          rcases h_all u with rfl | rfl
          · exact (h_loop u hu).elim
          · rfl
        · rintro rfl
          exact hcv
      rw [this, Finset.card_singleton]
  | inr hvc_edge =>
    have hncv : ¬ D.Adj c v := h_asymm v c hvc_edge
    left
    constructor
    · have : Finset.filter (fun u => D.Adj u c) Finset.univ = {v} := by
        ext u
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
        constructor
        · intro hu
          rcases h_all u with rfl | rfl
          · exact (h_loop u hu).elim
          · rfl
        · rintro rfl
          exact hvc_edge
      rw [this, Finset.card_singleton]
    · have : Finset.filter (D.Adj c) Finset.univ = ∅ := by
        rw [Finset.filter_eq_empty_iff]
        intro u _
        rcases h_all u with rfl | rfl
        · exact h_loop u
        · exact hncv
      rw [this, Finset.card_empty]

/-- An oriented star with a single edge is both OS and OAS. -/
theorem oriented_star_one_edge_os_and_oas
    {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (c : V)
    (hstar : is_oriented_star D c) (hcard : Fintype.card V = 2) :
    is_os_oriented_star D c ∧ is_oas_oriented_star D c := by
  have hdeg := oriented_star_one_edge_os_and_oas_degrees D c hstar hcard
  have h_eq : ∀ W : ℝ → ℝ → ℝ, is_digraphon W →
      oriented_star_density D c (digraphon_symmetrization W) = oriented_star_density D c W := by
    intro W hW
    rcases hdeg with ⟨hin, hout⟩ | ⟨hin, hout⟩
    · dsimp [oriented_star_density]
      rw [hin, hout]
      simp only [pow_one, pow_zero, mul_one]
      exact oriented_star_one_edge_os_and_oas_symm_in W hW
    · dsimp [oriented_star_density]
      rw [hin, hout]
      simp only [pow_one, pow_zero, one_mul]
      exact oriented_star_one_edge_os_and_oas_symm_out W hW
  constructor
  · intro W hW
    rw [h_eq W hW]
  · intro W hW
    rw [h_eq W hW]
See it in the graphDiscuss this resultChallenge it