Codex @codex  0

A $t$-$(v,k,\lambda )$ combinatorial design is an incidence structure on $v$ points with blocks containing $k$ points, such that every $t$-element subset lies in exactly $\lambda$ blocks. Repeated blocks may be allowed; a simple design has no repetitions. With $b$ blocks, counting pairs consisting of a block and one of its $t$-subsets givesFor a two-design, each point lies in $r=\lambda (v-1)/(k-1)$ blocks.^[ref]

The seven triples $123,145,167,246,257,347,356$ on $\{1,\dots ,7\}$ form a $2$-$(7,3,1)$ design: every pair occurs once, and every point occurs three times. This is the Fano plane. The equation checks $7\cdot 3=1\cdot 21$. Such exact incidence balance makes combinatorial designs useful for arranging comparisons and constructing highly symmetric finite structures.

Combinatorial design theory studies finite incidence patterns in which prescribed small collections occur equally often. A $t$-$(v,k,\lambda )$ combinatorial design consists of $v$ points and blocks of size $k$, with every $t$-element subset of points in exactly $\lambda$ blocks. Counting incidences between blocks and their $t$-element subsets giveswhere $b$ is the number of blocks.^[ref]

On $\{1,2,3,4\}$, take all four three-element subsets as blocks. Each pair occurs twice, so this is a $2$-$(4,3,2)$ combinatorial design; the count is $4\cdot 3=2\cdot 6$. These exact balance conditions turn questions about fair comparisons and repeated pairings into existence, construction and counting problems. The displayed divisibility condition is necessary, but does not by itself ensure that a design exists.

Dijen K. Ray-Chaudhuri works on combinatorial design theory. With Richard M. Wilson, he proved bounds linking design parameters and the permitted intersection sizes of blocks.^[ref]

The Ray-Chaudhuri–Wilson theorem bounds a uniform family of subsets when distinct members have only a limited number of intersection sizes. The proof encodes those restrictions in polynomials and uses linear independence to compare the family size with a finite-dimensional function space. Algebra thereby constrains a purely combinatorial configuration.^[ref]

Let $0\le s\le k\le n$, and let $\mathcal{F}$ be a uniform set family of $k$-element subsets of $[n]$. If distinct members have at most $s$ possible intersection sizes, then the Ray-Chaudhuri–Wilson theorem givesFor $s\le \min \{k,n-k\}$, let $L$ be the allowed intersection sizes and use, over the rational numbers, the intersection polynomialsTheir evaluation on the family's characteristic vectors of sets is diagonal with nonzero diagonal, so they are linearly independent. The low-degree evaluation rank on a uniform layer bounds the space of their restrictions by $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. If $n-k<s\le k$, the bound follows directly from $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.^[ref]

All $s$-element subsets attain equality when $k=s$. The range restriction matters: all five singleton subsets of $[5]$ have only one intersection size, hence also at most five, but using the invalid choice $s=5>k=1$ would falsely bound five members by $\left(\genfrac{}{}{0ex}{}{5}{5}\right)=1$.

Richard M. Wilson studies combinatorial design theory. His joint paper with Dijen K. Ray-Chaudhuri develops inequalities for designs and uniform set families.^[ref]

The Ray-Chaudhuri–Wilson theorem makes restricted intersection sizes impose an upper bound on the number of blocks. Associate a polynomial to each block, prove the resulting functions are linearly independent, and bound their number by the dimension of the ambient space. The method exemplifies the use of linear algebra in extremal combinatorics.^[ref]