Theorems · Theorem · combinatorics

SimpleGraph.farFromTriangleFree_of_disjoint_triangles

∀ {α : Type u_1} {𝕜 : Type u_3} [inst : Field 𝕜] [inst_1 : LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {G : SimpleGraph α}
  {ε : 𝕜} [inst_3 : Fintype α] [inst_4 : DecidableRel G.Adj] [inst_5 : DecidableEq α],
  ∀ tris ⊆ G.cliqueFinset 3,
    ((↑tris).Pairwise fun x y => (↑x ∩ ↑y).Subsingleton) →
      ε * ↑(Fintype.card α ^ 2) ≤ ↑tris.card → G.FarFromTriangleFree ε

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

Defined in

Mathlib.Combinatorics.SimpleGraph.Triangle.Basic

Cited by

2 results in Mathlib

Foundations

Depth 82 from the axioms · uses propext, Classical.choice, Quot.sound

Assumes

FieldLinearOrderIsStrictOrderedRingFintypeDecidableRelDecidableEq