§2.1, p. 7 — properties A, B, C of a type-3 maximal clique, and maximality in G[N(v) ∩ N(u)]
ProvedCClosedGraphs.Peeling.type_three_structurec-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph, a set of vertices, , and let be a maximal clique of of type 3: and is not a maximal clique of . Then
- (A) ;
- (B) no vertex outside is adjacent to every vertex of ;
- (C) there is a vertex , , not adjacent to , which is adjacent to every vertex of , and for this
These are the three properties of a type-3 clique stated on p. 7 of the paper, together with the consequence that is maximal in ; they are what lets one charge each type-3 clique to a pair .
Formalization Note "Property C: a vertex " is read as , as in Figure 2 and in the sum (1); the paper's is the neighbourhood in the current graph , so all vertices are taken in .
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
theorem type_three_structure {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(W : Set V) (v : V) (hv : v ∈ W) (K : Finset V) (hK : K ∈ maxCliquesIn G W)
(hvK : v ∈ K) (h3 : K.erase v ∉ maxCliquesIn G (W \ {v})) :
(↑(K.erase v) : Set V) ⊆ G.neighborSet v ∧
(∀ w ∈ W ∩ G.neighborSet v, w ∉ K → ¬ ∀ x ∈ K.erase v, G.Adj w x) ∧
∃ u ∈ W, u ≠ v ∧ ¬ G.Adj v u ∧ (∀ x ∈ K.erase v, G.Adj u x) ∧
K.erase v ∈ maxCliquesIn 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, proof of Theorem 2.1 (properties A–C and the paragraph after them; Figure 2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.