Lemma 3.2, p. 9 — the neighbourhood of a vertex induces a (c−1)-closed graph
ProvedCClosedGraphs.Improved.lemma_3_2c-closed-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a graph and a vertex set such that is -closed, and let . Then the neighbourhood of inside induces a -closed graph:
The paper states this for ("For any , is a -closed graph"); the relative form is what the induction on induced subgraphs uses. It lowers the closure parameter by one, which drives the induction on in Theorem 3.1.
Formalization Note is natural-number subtraction, safe because . For the conclusion says that is a clique.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
theorem lemma_3_2 {V : Type*} [Fintype V] [DecidableEq V] {c : ℕ} (hc : 0 < c)
{G : SimpleGraph V} {W : Set V} (hW : IsCClosedOn c G W) {v : V} (hv : v ∈ W) :
IsCClosedOn (c - 1) 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, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.