§2.1, p. 6 — maximal cliques of types 1 and 2 number at most those of G \ {v}
ProvedCClosedGraphs.Peeling.types_one_two_lec-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph, a set of vertices and . Call a maximal clique of of type 1 if , and of type 2 if and is a maximal clique of . Then
In the paper (, ) this is the step "the number of maximal cliques of types 1 and 2 combined is at most " of the peeling argument. It holds for every graph; no closure hypothesis is involved.
Formalization Note The induced subgraph of the current graph is ; the right-hand side is the actual number of maximal cliques of that graph, which is at most the paper's when is -closed.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
open Classical in
theorem types_one_two_le {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
≤ numMaxCliquesIn G (W \ {v}) := 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. 6, §2.1, proof of Theorem 2.1 (types 1–3 and the bound on types 1 and 2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.