Theorem 2.2 — a weakly c-closed graph on n vertices has at most 3^{(c−1)/3} n² maximal cliques
ProvedCClosedGraphs.Peeling.theorem_2_2For all positive integers and , every weakly -closed graph on vertices has at most
maximal cliques. Here is weakly -closed if its vertices can be ordered so that each is in no bad pair (a non-adjacent pair with at least common neighbours) of the subgraph induced by .
This is Theorem 2.2 (= Theorem 1.5) of the paper. Weak -closure is a robust form of triadic closure: real social networks with thousands of vertices are weakly -closed for small even when they are -closed only for large . The theorem makes the number of maximal cliques, and hence the cost of enumerating them, polynomial in for fixed on this class.
Formalization Note Graphs on vertices are simple graphs on Fin n; the ordering is a permutation of Fin n; common neighbours in the bad-pair condition are counted inside . is a real power. The hypothesis is the paper's and is needed: the graph with no vertices has one maximal clique, the empty one.
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
namespace CClosedGraphs.Peeling
theorem theorem_2_2 (c n : ℕ) (hc : 0 < c) (hn : 0 < n) (G : SimpleGraph (Fin n))
(hG : IsWeaklyCClosed c G) :
(numMaxCliques G : ℝ) ≤ (3 : ℝ) ^ (((c : ℝ) - 1) / 3) * (n : ℝ) ^ 2 := by sorry
end CClosedGraphs.Peeling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.