§3, Case 1, p. 9 — maximal cliques through v correspond to maximal cliques of G[N(v)]
ProvedCClosedGraphs.Improved.card_maxCliques_mem_eqmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any graph, a vertex set and . The number of maximal cliques of that contain equals the number of maximal cliques of the neighbourhood of in :
This is the identity behind the Case 1 bound (sum it over ) and behind the bound " is in at most maximal cliques" in Case 2. No closure hypothesis is needed. When has no neighbour in both sides equal : the clique on the left, the empty clique on the right.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
theorem card_maxCliques_mem_eq {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Set V) {v : V} (hv : v ∈ W) :
((CClosedGraphs.Peeling.maxCliquesIn G W).filter (fun K => v ∈ K)).card =
CClosedGraphs.Peeling.numMaxCliquesIn G (W ∩ G.neighborSet v) := 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. 9, proof of Theorem 3.1, Case 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.