Welzl orders

Lax195003.WelzlOrders Β· 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.

    Natural Language Statement

    Definition

    Let F\mathcal{F} be a set system on a finite ground set. A set X∈FX ∈ \mathcal{F} 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 F\mathcal{F}. A Welzl order of crossing number at most k is a total order whose crossing number is at most k.

    Concept map
    1 concept; 6 descendants hidden
    100%
    Proven claimOpen claimDefinitionThis conceptRelated conceptA β†’ B: B builds on A

    In the paper

    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 nβˆ’1n - 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.

    Discussion

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

    Loading discussion…