Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax195003.WelzlOrders

Welzl orders

concepts/Lax195003/WelzlOrders.lean · lax-195003

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.

    Concept map

    Proven claimOpen claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    Let 𝓕𝓕 be a set system on a finite ground set. A set X𝓕X ∈ 𝓕 crosses a total order whenever two consecutive elements lie on opposite sides of XX. Its crossing count is the number of such consecutive pairs, and the crossing number of the order is the largest crossing count over all sets in 𝓕𝓕. A Welzl order of crossing number at most k is a total order whose crossing number is at most k.

    Lean source view on GitHub

    1import Mathlib.Data.Fin.Basic
    2import Mathlib.Data.Nat.Lattice
    3import Mathlib.Data.Set.Card
    4
    5/-!
    6---
    7title: Welzl orders
    8type: definition
    9---
    10Let `𝓕` be a set system on a finite ground set. A set `X ∈ 𝓕` crosses
    11a total order whenever two consecutive elements lie on opposite sides of
    12`X`. Its crossing count is the number of such consecutive pairs, and the
    13crossing number of the order is the largest crossing count over all sets in
    14`𝓕`. A Welzl order of crossing number at most *k* is a total order whose
    15crossing number is at most *k*.
    16
    17# Formalization notes
    18
    19A total order of `Fin n` is represented by a permutation `π`, with `π v` the
    20position of `v`. Consecutive pairs are counted by their earlier endpoint:
    21`u` contributes exactly when some `v` has natural-number position
    22`(π u).val + 1` and precisely one of `u` and `v` lies in the set. Comparing
    23the natural values, rather than adding inside `Fin n`, avoids turning the
    24last and first positions into an artificial cyclic pair.
    25
    26The crossing number is a natural supremum. Every crossing count is at most
    27`n - 1`, so the set is bounded; for an empty family the natural convention
    28`sSup ∅ = 0` gives the expected crossing number zero. `IsWelzlOrder` is a
    29`Prop`-valued bound rather than a structure carrying data derivable from the
    30order and the set system.
    31
    32-/
    33
    34namespace Lax195003.WelzlOrders
    35
    36/-- A set system on `α`: a family of subsets of the ground set `α`. -/
    37abbrev SetSystem (α : Type*) := Set (Set α)
    38
    39/-- The number of consecutive pairs in the order `π` with exactly one
    40endpoint in `X`. -/
    41noncomputable def crossingCount {n : ℕ} (π : Equiv.Perm (Fin n))
    42 (X : Set (Fin n)) : ℕ :=
    43 {u : Fin n | ∃ v : Fin n,
    44 (π v).val = (π u).val + 1 ∧ (u ∈ X ↔ v ∉ X)}.ncard
    45
    46/-- The crossing number of `π` with respect to `𝓕`: the largest crossing
    47count of a member of the set system. -/
    48noncomputable def crossingNumber {n : ℕ} (𝓕 : SetSystem (Fin n))
    49 (π : Equiv.Perm (Fin n)) : ℕ :=
    50 sSup {k : ℕ | ∃ X ∈ 𝓕, k = crossingCount π X}
    51
    52/-- The order `π` is a Welzl order of crossing number at most `k` for the
    53set system `𝓕`. -/
    54def IsWelzlOrder {n : ℕ} (𝓕 : SetSystem (Fin n))
    55 (π : Equiv.Perm (Fin n)) (k : ℕ) : Prop :=
    56 crossingNumber 𝓕 π ≤ k
    57
    58end Lax195003.WelzlOrders
    59

    Formalization notes

    A total order of FinnFin n is represented by a permutation ππ, with πvπ v the position of vv. Consecutive pairs are counted by their earlier endpoint: uu contributes exactly when some vv has natural-number position (πu).val+1(π u).val + 1 and precisely one of uu and vv lies in the set. Comparing the natural values, rather than adding inside FinnFin n, avoids turning the last and first positions into an artificial cyclic pair.

    The crossing number is a natural supremum. Every crossing count is at most n1n - 1, so the set is bounded; for an empty family the natural convention sSup=0sSup ∅ = 0 gives the expected crossing number zero. IsWelzlOrderIsWelzlOrder is a PropProp-valued bound rather than a structure carrying data derivable from the order and the set system.

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…