combinatorial design


Combinatorial design is a generic term for combinatorial structures described by families of finite sets satisfying some symmetries or other combinatorial properties of mutual arrangement. For example, the block designs generically describe a set with family of subsets satisfying some combinatorial properties.

A concrete structures of this kind are block tt-designs: if tt is an integer a tt-design is a set XX with a family of kk-element subsets of XX (called blocks) such that every xXx\in X appears in exactly rr blocks, and every tt-element subset TT appears in exactly λ\lambda blocks. One also says t(v,k,λ)t-(v,k,\lambda)-design if vv is the cardinality of XX. The number of blocks bb and rr are determined by the other data. The applications include algebraic codes, finite geometries, algorithm design etc.

(Non)existence of combinatorial designs with specific properties often has profound consequences on classification of various other mathematical structures (not necessarily finite ones); in particular lattices, finite geometries, finite groups etc.


Related nnLab items: binary linear code, synthetic projective geometry, Joyal species, matroid, building, incidence geometry

  • wikipedia: combinatorial design
  • Handbook of Combinatorial Designs, CRC Press 2006
  • P. Dembowski, Finite geometries, Springer-Verlag 1968
  • Jens Zumbrägel, Designs and codes in affine geometry, arXiv:1605.03789
  • Peter Keevash, The existence of designs, pdf

We prove the existence conjecture for combinatorial designs, answering a question of Steiner from 1853. More generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition.

category: combinatorics

Last revised on November 18, 2018 at 10:46:12. See the history of this page for a list of all contributions to it.