Neighborhood diversity
Lax825442.NeighborhoodDiversity · concepts/Lax825442/NeighborhoodDiversity.lean · lax-825442
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The neighborhood diversity of a graph is the minimum number of parts in a partition of its vertex set such that each part induces a clique or an independent set and is a module: its vertices have the same neighbors outside the part. The empty graph has neighborhood diversity zero.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Finite |
| 2 | import Mathlib.Data.Set.Card |
| 3 | import Mathlib.Order.Lattice.Nat |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Neighborhood diversity |
| 8 | type: definition |
| 9 | --- |
| 10 | The neighborhood diversity of a graph is the minimum number of parts in a |
| 11 | partition of its vertex set such that each part induces a clique or an |
| 12 | independent set and is a module: its vertices have the same neighbors outside |
| 13 | the part. The empty graph has neighborhood diversity zero. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax825442.NeighborhoodDiversity |
| 17 | |
| 18 | /-- A partition into `k` parts, each a module and each inducing a clique or |
| 19 | an independent set. Empty labels are allowed and disappear at the minimum. -/ |
| 20 | def HasNeighborhoodDiversityAtMost {V : Type} [Fintype V] [DecidableEq V] |
| 21 | (G : SimpleGraph V) (k : ℕ) : Prop := |
| 22 | ∃ part : V → Fin k, |
| 23 | (∀ u v w : V, |
| 24 | (part u = part v ∧ part w ≠ part u) → (G.Adj u w ↔ G.Adj v w)) ∧ |
| 25 | (∀ i : Fin k, |
| 26 | (∀ u v : V, |
| 27 | (u ≠ v ∧ (part u = i ∧ part v = i)) → G.Adj u v) ∨ |
| 28 | (∀ u v : V, |
| 29 | (part u = i ∧ part v = i) → ¬ G.Adj u v)) |
| 30 | |
| 31 | /-- The minimum number of neighborhood-diversity parts. -/ |
| 32 | noncomputable def neighborhoodDiversity {V : Type} [Fintype V] [DecidableEq V] |
| 33 | (G : SimpleGraph V) : ℕ := |
| 34 | sInf {k | HasNeighborhoodDiversityAtMost G k} |
| 35 | |
| 36 | end Lax825442.NeighborhoodDiversity |
| 37 |
Builds on
none
Used by
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments