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 #
IncidenceSystem: An incidence system consists of a carrier set and subsets called blocks.IncidenceSystem.IsSimple: An incidence system is simple if there are no duplicate blocks.IncidenceSystem.IsUniform: An incidence system isk-uniform if every block has sizek.
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 #
- Define regular (number of blocks containing a given point is fixed)
- Define equidistance (pairwise intersections have a given size)
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α. The blocks must be subsets of the ambient set.
Instances For
Every hypergraph can be viewed as an incidence system where the hyperedges become the blocks.
Equations
Instances For
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
The discrete incidence system consists of singleton blocks.
Equations
Instances For
The indiscrete incidence system consists of the carrier as a single block.
Equations
Instances For
An incidence system is simple if there are no duplicate blocks.