Documentation

Mathlib.Combinatorics.Design.Defs

Combinatorial Designs #

This file defines incidence systems and combinatorial designs.

An incidence system consists of a carrier set and subsets called blocks. We index our blocks by a subset of an indexing type to make it easy to add and remove blocks if desired. Duplicate blocks are permitted unless IncidenceSystem.IsSimple is imposed.

Note the similarity with Hypergraph which consists of a carrier set and subsets called sets. The primary difference is that Hypergraph edges are not indexed and do not allow for duplication.

Main definitions #

Implementation details #

We place everything in the IncidenceSystem namespace, because this still allows one to write {α β : Type*} (d : Design α β) [d.IsSimple] [d.IsUniform].

We index our blocks by a subset of an indexing type β to make it easy to add and remove blocks if desired. Duplicate blocks are permitted unless IncidenceSystem.IsSimple is imposed.

TODO #

structure IncidenceSystem (α : Type u_1) (β : Type u_2) :
Type (max u_1 u_2)

An incidence system consists of a carrier set and subsets called blocks. We index our blocks by a subset of an indexing type β to make it easy to add and remove blocks if desired. Duplicate blocks are permitted unless IncidenceSystem.IsSimple is imposed.

  • carrier : Set α

    The ambient set for the incidence system.

  • blockSet : Set β

    The indexing set for the blocks.

  • block (b : β) : Set α

    The function from the indexing type β to the blocks in α.

  • block_subset {b : β} (hb : b ∈ self.blockSet) : self.block b ⊆ self.carrier

    The blocks must be subsets of the ambient set.

Instances For
    theorem IncidenceSystem.biUnion_block_subset {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) :
    ⋃ b ∈ d.blockSet, d.block b ⊆ d.carrier
    theorem IncidenceSystem.mem_of_mem_block {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) {b : β} {x : α} (hx : x ∈ d.block b) (hb : b ∈ d.blockSet) :

    Every hypergraph can be viewed as an incidence system where the hyperedges become the blocks.

    Equations
    Instances For
      @[simp]
      theorem IncidenceSystem.block_ofHypergraph {α : Type u_1} (H : Hypergraph α) (x : Set α) :
      def IncidenceSystem.toHypergraph {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) :

      Every incidence system can be viewed as a hypergraph where the blocks become the hyperedges. Note that hypergraphs are simple in mathlib, so this function will collapse duplicate blocks.

      Equations
      Instances For
        def IncidenceSystem.discrete {α : Type u_1} (s : Set α) :

        The discrete incidence system consists of singleton blocks.

        Equations
        Instances For
          @[simp]
          theorem IncidenceSystem.block_discrete {α : Type u_1} (s : Set α) (x : α) :
          @[simp]
          theorem IncidenceSystem.carrier_discrete {α : Type u_1} (s : Set α) :
          @[simp]
          theorem IncidenceSystem.blockSet_discrete {α : Type u_1} (s : Set α) :
          def IncidenceSystem.indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) :

          The indiscrete incidence system consists of the carrier as a single block.

          Equations
          Instances For
            @[simp]
            theorem IncidenceSystem.block_indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b x✝ : β) :
            (indiscrete s b).block x✝ = s
            @[simp]
            theorem IncidenceSystem.blockSet_indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) :
            @[simp]
            theorem IncidenceSystem.carrier_indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) :
            class IncidenceSystem.IsSimple {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) :

            An incidence system is simple if there are no duplicate blocks.

            Instances
              @[simp]
              @[simp]
              theorem IncidenceSystem.IsSimple.indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) :
              structure IncidenceSystem.IsUniform {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) (k : ℕ) :

              An incidence system is k-uniform if every block has size k.

              Instances For
                theorem IncidenceSystem.isUniform_iff {α : Type u_1} {β : Type u_2} (d : IncidenceSystem α β) (k : ℕ) :
                d.IsUniform k ↔ ∀ {b : β}, b ∈ d.blockSet → (d.block b).ncard = k
                @[simp]
                theorem IncidenceSystem.IsUniform.discrete {α : Type u_1} (s : Set α) :
                @[simp]
                theorem IncidenceSystem.IsUniform.indiscrete {α : Type u_1} {β : Type u_2} (s : Set α) (b : β) :
                theorem IncidenceSystem.IsUniform.nonempty_block {α : Type u_1} {β : Type u_2} {d : IncidenceSystem α β} {k : ℕ} (hd : d.IsUniform k) (hk : k ≠ 0) {b : β} (hb : b ∈ d.blockSet) :
                theorem IncidenceSystem.IsUniform.finite_block {α : Type u_1} {β : Type u_2} {d : IncidenceSystem α β} {k : ℕ} (hd : d.IsUniform k) (hk : k ≠ 0) {b : β} (hb : b ∈ d.blockSet) :