Theorem 3.1, p. 8 — a c-closed graph on n vertices has at most 4^{(c+4)(c−1)/2} n^{2−2^{1−c}} maximal cliques
ProvedCClosedGraphs.Improved.theorem_3_1c-closed-graphextremal-graph-theorymaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be positive integers and let be a -closed graph on vertices, that is, any two distinct vertices with at least common neighbours are adjacent. Then the number of maximal cliques of satisfies
Equivalently , where is the maximum number of maximal cliques of a -closed graph on vertices. For fixed the bound is : for , for , for , which together with the bound of Theorem 2.1 gives Theorem 1.4.
Formalization Note The vertex set is Fin n. A maximal clique is a vertex set that is a clique and is not contained in a larger clique. Both powers are real powers.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
theorem theorem_3_1 (c n : ℕ) (hc : 0 < c) (hn : 0 < n) (G : SimpleGraph (Fin n))
(hG : CClosedGraphs.Peeling.IsCClosed c G) :
(CClosedGraphs.Peeling.numMaxCliques G : ℝ) ≤
(4 : ℝ) ^ (((c : ℝ) + 4) * ((c : ℝ) - 1) / 2) *
(n : ℝ) ^ ((2 : ℝ) - (2 : ℝ) ^ (1 - (c : ℝ))) := 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. 8, Theorem 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.