combinatorial design

- binary linear code
- chord diagram
- combinatorial design
- graph
- Latin square
- matroid
- partition
- permutation
- shuffle
- tree
- Young diagram

category: combinatorics

**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 $t$-designs: if $t$ is an integer a **$t$-design** is a set $X$ with a family of $k$-element subsets of $X$ (called blocks) such that every $x\in X$ appears in exactly $r$ blocks, and every $t$-element subset $T$ appears in exactly $\lambda$ blocks. One also says $t-(v,k,\lambda)$-design if $v$ is the cardinality of $X$. The number of blocks $b$ and $r$ 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 $n$Lab 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.