Documentation

LeanPool.DrossFractionalTriangleDecomposition.Internal.EdgeCountBound

The exact edge-count bound #

Split the degree sum into vertices of degree at least minDegree + 2 and the remaining vertices. The sharpened high-degree count supplies the linear correction in Dross's exact cut inequality.

theorem LeanPool.DrossFractionalTriangleDecomposition.mbound_tight {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (δ : ℝ) (h : 9 * Fintype.card V ≤ 10 * G.minDegree) (hn20 : 20 ≤ Fintype.card V) (hδeq : ↑(Fintype.card V) - ↑G.minDegree = δ * ↑(Fintype.card V)) (hδn2 : 2 ≤ δ * ↑(Fintype.card V)) (hnb : ↑{v : V | G.minDegree + 2 ≤ G.degree v}.card ≤ 2 * δ * ↑(Fintype.card V) - 4) :
2 * ↑G.edgeFinset.card ≤ (1 - δ + 2 * δ ^ 2) * ↑(Fintype.card V) ^ 2 + 4 + ↑(Fintype.card V) - 6 * δ * ↑(Fintype.card V)