§2.1, p. 7 (cites [45]) — any k-vertex graph has at most 3^{k/3} maximal cliques
ProvedCClosedGraphs.Peeling.moon_moserextremal-graph-theorymaximal-cliquemoon-moserp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph and a set of of its vertices. The induced subgraph has at most maximal cliques:
This is the bound of Moon and Moser (1965) on the number of maximal cliques of a -vertex graph, in the form used on p. 7 of the paper, where it is applied to the induced subgraphs of fewer than vertices. Taking to be all vertices gives the bound for itself.
Formalization Note Stated for induced subgraphs (the relative form the proof applies); the exponent is a real number and the power is the real power. The sharp Moon–Moser values are not claimed.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Peeling_Setting
Formal statement
namespace CClosedGraphs.Peeling
theorem moon_moser {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (W : Set V) :
(numMaxCliquesIn G W : ℝ) ≤ (3 : ℝ) ^ ((W.ncard : ℝ) / 3) := 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 (citing Moon and Moser [45])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.