AFTD Auto-Formalizing Theoretical Domains

is_knrs

def

A graph F has the KNRS property if for every d in (0, 1] and every ε > 0, there exists ρ > 0 and n₀ such that every (ρ, d)-dense graph G on at least n₀ vertices has homomorphism density q(F, G) ≥ d^{e(F)} - ε.

Statement

def is_knrs {α : Type*} [Fintype α] (F : SimpleGraph α) : Prop
Defined in
arXiv:2610.13820, Conjecture 1.1
Verified
26 Oct 2026
Axioms
none listed
Built on 2
  • graph_hom_densityThe homomorphism density q(F, G) of a graph F in a graph G is the number of graph homomorphisms from F to G divided by |V(G)|^{|V(F)|}.
  • is_locally_denseA graph G is (ρ, d)-dense if every vertex subset U of size at least ρ * |V(G)| spans at least (d / 2) * |U|^2 edges.

Read back from the Lean

A predicate is_knrs on a simple graph F on a finite type α asserting that: for every real number $d$ such that $0 < d \le 1$, and for every real number $\varepsilon > 0$, there exists a real number $\rho > 0$ and a natural number $n_0$ such that for all natural numbers $n \ge n_0$, and for every simple graph $G$ on vertex type Fin n, if $G$ is locally dense with parameters $\rho$ and $d$ (that is, for every finset $U \subseteq \text{Fin } n$ with $|U| \ge \rho n$, the induced subgraph $G[U]$ has at least $\frac{d}{2} |U|^2$ edges), then the homomorphism density of $F$ into $G$ is at least $d^{|E(F)|} - \varepsilon$, where $|E(F)|$ is the number of edges of $F$.

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 KNRS property for a graph F: homomorphism density in locally dense graphs is asymptotically bounded below by d^{e(F)}. -/
def is_knrs {α : Type*} [Fintype α] (F : SimpleGraph α) : Prop := ∀ (d : ℝ), 0 < d → d ≤ 1 → ∀ (ε : ℝ), 0 < ε →
    ∃ (ρ : ℝ), 0 < ρ ∧ ∃ (n₀ : ℕ), ∀ (n : ℕ), n₀ ≤ n →
      ∀ (G : SimpleGraph (Fin n)), is_locally_dense G ρ d →
        d ^ (Nat.card F.edgeSet) - ε ≤ graph_hom_density F G
See it in the graphDiscuss this resultChallenge it