§2.1, pp. 7–8 — peeling a vertex in no bad pair: F(n, c) ≤ F(n − 1, c) + 3^{(c−1)/3} n
ProvedCClosedGraphs.Peeling.peel_stepc-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weakly-c-closed
Let be a positive integer, a finite simple graph, a set of vertices and a vertex that is in no bad pair of , i.e. every , , not adjacent to has fewer than common neighbours with inside . Then
This is the recursive inequality of the proof of Theorem 2.1, in the form of the remark after it: "the proof is valid as long as for all vertices ", so each recursive level only needs a vertex in no bad pair. Iterating it along the ordering of a weakly -closed graph proves Theorem 2.2.
Formalization Note The paper's is , the number of vertices of the current graph ; is a real power.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
theorem peel_step {V : Type*} [Fintype V] [DecidableEq V] (c : ℕ) (hc : 0 < c)
(G : SimpleGraph V) (W : Set V) (v : V) (hv : v ∈ W)
(hbad : ∀ w : V, ¬ IsBadPairIn c G W v w) :
(numMaxCliquesIn G W : ℝ) ≤
(numMaxCliquesIn G (W \ {v}) : ℝ) + (3 : ℝ) ^ (((c : ℝ) - 1) / 3) * (W.ncard : ℝ) := by sorry
end CClosedGraphs.Peeling
Source
Fox, Roughgarden, Seshadhri, Wei and Wein, Finding cliques in social networks: a new distribution-free model, arXiv:1804.07431v1, pp. 7–8, §2.1, proof of Theorem 2.1 (recursive inequality) and the remark after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.