§2.1, p. 7, (1) — type-3 cliques number at most Σ_u F(|N(u) ∩ N(v)|, c)
ProvedCClosedGraphs.Peeling.ineq_1c-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph, a set of vertices and . The number of maximal cliques of of type 3 ( and not maximal in ) satisfies
This is inequality (1) of the paper, with each replaced by the actual number of maximal cliques of , which is at most since induced subgraphs of a -closed graph are -closed. Combined with the Moon–Moser bound it gives the term of the recursion.
Formalization Note The sum runs over the finite set of with and not adjacent to ; neighbourhoods are taken in .
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
open Classical in
theorem ineq_1 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(W : Set V) (v : V) (hv : v ∈ W) :
((maxCliquesIn G W).filter
(fun K => v ∈ K ∧ K.erase v ∉ maxCliquesIn G (W \ {v}))).card
≤ ∑ u ∈ W.toFinset.filter (fun u => u ≠ v ∧ ¬ G.Adj v u),
numMaxCliquesIn G (W ∩ G.commonNeighbors v u) := 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, p. 7, §2.1, display (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.