pp. 10–11 — the recurrence's two cases are bounded by F₀(n, c)
ProvedCClosedGraphs.Improved.recurrence_boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-inequality
Let be an integer and let be real numbers with and . With :
- if , then ;
- if , then
These are the two inequalities "we need to show" in the inductive step of Theorem 3.1: the right-hand sides of the recurrence for , with at the smaller parameters replaced by , do not exceed .
Formalization Note The paper prints this display with base in place of the base of ; the statement here uses as the paper defines it on p. 10. The second case keeps the paper's (the vertex itself is also deleted, so would suffice); .
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
theorem recurrence_bound {c : ℕ} (hc : 2 ≤ c) {n Δ : ℝ} (hn : 1 ≤ n) (hΔ0 : 0 < Δ)
(hΔn : Δ ≤ n) :
(Δ ≤ Real.sqrt n → n * F0 Δ (c - 1) ≤ F0 n c) ∧
(Real.sqrt n < Δ → F0 Δ (c - 1) * (n / Δ) * 2 ^ c + F0 (n - Δ) c ≤ F0 n c) := by sorry
end CClosedGraphs.Improved
Source
Fox, Roughgarden, Seshadhri, Wei and Wein, Finding cliques in social networks: a new distribution-free model, arXiv:1804.07431v1, pp. 10–11, proof of Theorem 3.1, recurrence and inductive-case display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.