lt_half — Mathlib

English

If there are ε*(card α)^2 many pairwise disjoint triangles, the graph is ε-far from triangle-free.

Русский

Если существует ε*(|α|)^2 много попарно несмежных треугольников, граф далёк от треугольников.

LaTeX

$$$\\text{tris big} \\Rightarrow G.\\text{FarFromTriangleFree } ε$$$

Lean4

theorem lt_half (hε : G.FarFromTriangleFree ε) : ε < 2⁻¹ :=
  by
  refine lt_of_mul_lt_mul_right (α := 𝕜) (a := Fintype.card α ^ 2) ?_ (by positivity)
  calc
    ε * Fintype.card α ^ 2
    _ ≤ #G.edgeFinset := by simpa using hε.le_card_edgeFinset (by simp)
    _ ≤ (Fintype.card α).choose 2 := by gcongr; exact card_edgeFinset_le_card_choose_two
    _ < 2⁻¹ * Fintype.card α ^ 2 := by simpa [← div_eq_inv_mul] using Nat.choose_lt_pow_div (by positivity) le_rfl

Похожие утверждения