Inequality (3), p. 9 — Σ_S |N(S) ∩ N₂(v)| ≤ |N₂(v)| 2^{c−1} ≤ min{Δ², n} 2^{c−1}
ProvedCClosedGraphs.Improved.ineq_3c-closed-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be -closed, let , and let bound the degree in of every vertex of . With and as in the setting (computed in ) and ,
The first inequality holds because a vertex is not adjacent to , so and have fewer than common neighbours and lies in for few sets . Together the two give inequality (3), the constraint under which the sum (2) is maximised.
Formalization Note is any common upper bound on the degrees in (the paper takes the maximum degree). The sum runs over non-empty , matching the definition of ; this only strengthens the paper's display. All quantities are natural numbers.
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_Improved_Setting
Formal statement
namespace CClosedGraphs.Improved
open Classical in
theorem ineq_3 {V : Type*} [Fintype V] [DecidableEq V] {c : ℕ} (hc : 0 < c)
{G : SimpleGraph V} {W : Set V} (hW : IsCClosedOn c G W) {v : V} (hv : v ∈ W)
(Δ : ℕ) (hΔ : ∀ x ∈ W, (W ∩ G.neighborSet x).ncard ≤ Δ) :
(∑ S ∈ (Finset.univ.filter (fun x => x ∈ W ∧ G.Adj v x)).powerset.filter
(fun S => S.Nonempty),
(commonNbrs G S ∩ dist2In G W v).ncard) ≤ (dist2In G W v).ncard * 2 ^ (c - 1) ∧
(dist2In G W v).ncard ≤ min (Δ ^ 2) W.ncard := 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 (3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.