Inequality (2), p. 9 β |π¦| β€ Ξ£_S F(|N(S) β© Nβ(v)|, cβ1)
ProvedCClosedGraphs.Improved.ineq_2c-closed-graphmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any graph, a vertex set and ; neighbourhoods and the second neighbourhood are taken in . Let be the set of maximal cliques of that do not contain but contain some neighbour of . Then
where .
This is inequality (2) of the proof of Theorem 3.1, with replaced by the actual number of maximal cliques of ; the -closedness of these graphs, which turns the count into , is used in the Case 2 count. It groups the cliques by .
Formalization Note The sum runs over non-empty , as the paper defines only for non-empty ; this makes the bound stronger than a sum over all . No closure hypothesis is needed.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
open Classical in
theorem ineq_2 {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Set V) {v : V} (hv : v β W) :
((CClosedGraphs.Peeling.maxCliquesIn G W).filter (fun K => v β K β§ β y β K, G.Adj v y)).card β€
β S β (Finset.univ.filter (fun x => x β W β§ G.Adj v x)).powerset.filter
(fun S => S.Nonempty),
CClosedGraphs.Peeling.numMaxCliquesIn G (commonNbrs G S β© dist2In G W v) := 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. 9, proof of Theorem 3.1, Case 2, inequality (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.