Lax Lean Archive

Graph parameters and functional equivalence

Lax153141.GraphParameters · concepts/Lax153141/GraphParameters.lean · lax-153141

definition

Loading review…

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

    A graph parameter assigns a natural number to every finite simple graph. Two graph parameters p and q are functionally equivalent when each is bounded by a numerical function of the other: there are functions f, g : ℕ → ℕ such that every finite simple graph G satisfies both p(G) ≤ f(q(G)) and q(G) ≤ g(p(G)). Functionally equivalent parameters are bounded on exactly the same classes of graphs.

    Concept map
    1 concept; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Basic
    2
    3/-!
    4---
    5title: Graph parameters and functional equivalence
    6type: definition
    7---
    8A *graph parameter* assigns a natural number to every finite simple graph.
    9Two graph parameters *p* and *q* are *functionally equivalent* when each is
    10bounded by a numerical function of the other: there are functions
    11*f*, *g* : ℕ → ℕ such that every finite simple graph *G* satisfies both
    12*p*(*G*) ≤ *f*(*q*(*G*)) and *q*(*G*) ≤ *g*(*p*(*G*)). Functionally
    13equivalent parameters are bounded on exactly the same classes of graphs.
    14
    15# Formalization notes
    16
    17`GraphParam` is the uniform signature shared by all graph parameters in this
    18archive: a natural-valued function of finite simple graphs over `Fintype` and
    19`DecidableEq` instances. It is an abbreviation, so a statement about concrete
    20parameters mentions them by name — `Lax228581.TwinWidth.twinWidth`,
    21`Lax153141.MixedMinorNumber.mixedMinorNumber` — with no eta-expanded wrapper
    22lambdas a reader would have to unfold.
    23
    24The two directions of `FunctionallyEquivalent` are separate existential
    25claims rather than one function pair, so each can be established on its own.
    26-/
    27
    28namespace Lax153141.GraphParameters
    29
    30/-- A natural-valued parameter of finite simple graphs, in the uniform
    31signature shared by all graph parameters in this archive. -/
    32abbrev GraphParam :=
    33 ∀ {V : Type} [Fintype V] [DecidableEq V], SimpleGraph V → ℕ
    34
    35/-- Each of two graph parameters is bounded by a numerical function of the
    36other. -/
    37def FunctionallyEquivalent (p q : GraphParam) : Prop :=
    38 (∃ f : ℕ → ℕ, ∀ {V : Type} [Fintype V] [DecidableEq V]
    39 (G : SimpleGraph V), p G ≤ f (q G)) ∧
    40 (∃ g : ℕ → ℕ, ∀ {V : Type} [Fintype V] [DecidableEq V]
    41 (G : SimpleGraph V), q G ≤ g (p G))
    42
    43end Lax153141.GraphParameters
    44
    Formalization notes

    GraphParamGraphParam is the uniform signature shared by all graph parameters in this archive: a natural-valued function of finite simple graphs over FintypeFintype and DecidableEqDecidableEq instances. It is an abbreviation, so a statement about concrete parameters mentions them by name — Lax228581.TwinWidth.twinWidthLax228581.TwinWidth.twinWidth, Lax153141.MixedMinorNumber.mixedMinorNumberLax153141.MixedMinorNumber.mixedMinorNumber — with no eta-expanded wrapper lambdas a reader would have to unfold.

    The two directions of FunctionallyEquivalentFunctionallyEquivalent are separate existential claims rather than one function pair, so each can be established on its own.

    Builds on

    none

    Used by
    From Mathlib

    Discussion

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

    Loading discussion…