Weighted independent sets

Lax263307.WeightedIndependentSet · concepts/Lax263307/WeightedIndependentSet.lean · lax-263307

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    An instance consists of a finite simple graph and rational vertex weights. A solution is a vertex set together with its ambient number of vertices. The ambient number allows solutions for graphs of different orders to share one type; feasibility requires it to agree with the instance.

    An (1−ε)(1-\varepsilon)-approximation has weight at least (1−ε)w(J)(1-\varepsilon)w(J) for every independent set JJ. Weights may be negative, and the empty set is always feasible. All definitions here concern mathematical objects, independently of their machine representations.

    Concept map
    1 concept
    100%
    DefinitionThis conceptDescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Clique
    2import Mathlib.Data.Rat.Floor
    3
    4/-!
    5---
    6title: Weighted independent sets
    7type: definition
    8---
    9An instance consists of a finite simple graph and rational vertex weights.
    10A solution is a vertex set together with its ambient number of vertices.
    11The ambient number allows solutions for graphs of different orders to share
    12one type; feasibility requires it to agree with the instance.
    13
    14An (1−ε)(1-\varepsilon)-approximation has weight at least
    15(1−ε)w(J)(1-\varepsilon)w(J) for every independent set JJ.
    16Weights may be negative, and the empty set is always feasible.
    17All definitions here concern mathematical objects, independently of their
    18machine representations.
    19-/
    20
    21namespace Lax263307.WeightedIndependentSet
    22
    23/-- A finite graph with rational vertex weights. -/
    24structure Instance where
    25 order : ℕ
    26 graph : SimpleGraph (Fin order)
    27 weights : Fin order → ℚ
    28
    29/-- A vertex set in an explicitly specified finite ambient set. -/
    30abbrev Solution := (n : ℕ) × Finset (Fin n)
    31
    32/-- Total weight of a vertex set. -/
    33def weight {n : ℕ} (w : Fin n → ℚ) (I : Finset (Fin n)) : ℚ :=
    34 ∑ v ∈ I, w v
    35
    36/-- An independent set that achieves the requested multiplicative guarantee. -/
    37def IsApproximation {n : ℕ} (G : SimpleGraph (Fin n)) (w : Fin n → ℚ)
    38 (ε : ℚ) (I : Finset (Fin n)) : Prop :=
    39 G.IsIndepSet (I : Set (Fin n)) ∧
    40 ∀ J : Finset (Fin n), G.IsIndepSet (J : Set (Fin n)) →
    41 (1 - ε) * weight w J ≤ weight w I
    42
    43end Lax263307.WeightedIndependentSet
    44

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…