Inequality (4) and its consequence, p. 10 — cliques meeting N(v) ∪ {v} number at most F₀(Δ, c−1) min{Δ, n/Δ} 2^c
ProvedCClosedGraphs.Improved.case_2_countc-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be -closed with vertices, let bound the degree in of every vertex of , and let have degree exactly in , and assume (Case 2). Assume the inductive hypothesis at level : every non-empty vertex set with -closed satisfies . Then the number of maximal cliques of that contain at least one vertex of satisfies
This combines inequality (4), , with the bound on the cliques through . It is the high-degree step of the recurrence for .
Formalization Note The inductive hypothesis is an explicit premise and requires non-empty: the empty graph has one maximal clique while . All quantities on the right are real numbers; is real division.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
open Classical in
theorem case_2_count {V : Type*} [Fintype V] [DecidableEq V] {c : ℕ} (hc : 2 ≤ c)
{G : SimpleGraph V} {W : Set V} (hW : IsCClosedOn c G W) {v : V} (hv : v ∈ W)
(Δ : ℕ) (hΔpos : 1 ≤ Δ) (hΔ : ∀ x ∈ W, (W ∩ G.neighborSet x).ncard ≤ Δ)
(hv_deg : (W ∩ G.neighborSet v).ncard = Δ)
(hcase : Real.sqrt (W.ncard : ℝ) < (Δ : ℝ))
(hIH : ∀ W' : Set V, W'.Nonempty → IsCClosedOn (c - 1) G W' →
(CClosedGraphs.Peeling.numMaxCliquesIn G W' : ℝ) ≤ F0 (W'.ncard : ℝ) (c - 1)) :
((((CClosedGraphs.Peeling.maxCliquesIn G W).filter (fun K => v ∈ K ∨ ∃ y ∈ K, G.Adj v y)).card : ℕ) : ℝ) <
F0 (Δ : ℝ) (c - 1) * min (Δ : ℝ) ((W.ncard : ℝ) / (Δ : ℝ)) * 2 ^ 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, p. 10, proof of Theorem 3.1, Case 2, inequality (4) and the display after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.