is_knrs
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