Theorem 2.1 — a c-closed graph on n vertices has at most 3^{(c−1)/3} n² maximal cliques
ProvedCClosedGraphs.Peeling.theorem_2_1c-closed-graphextremal-graph-theorymaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For all positive integers and , every -closed graph on vertices has
maximal cliques; that is, .
This is the first bound of Theorem 1.4 of the paper: for fixed the number of maximal cliques of a -closed graph is polynomial in , in contrast with the maximal cliques an arbitrary graph can have. Theorem 2.2 extends it to weakly -closed graphs.
Formalization Note Graphs on vertices are simple graphs on Fin n; is a real power. The hypothesis is the paper's ("positive integers ").
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
theorem theorem_2_1 (c n : ℕ) (hc : 0 < c) (hn : 0 < n) (G : SimpleGraph (Fin n))
(hG : IsCClosed c G) :
(numMaxCliques G : ℝ) ≤ (3 : ℝ) ^ (((c : ℝ) - 1) / 3) * (n : ℝ) ^ 2 := 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, Theorem 2.1 (restatement of part of Theorem 1.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.