9 Designs

Definition

Let $\mathcal{S}=(\mathcal{P},\mathcal{B},I)$ be an incidence geometry where

• $\mathcal{P}$ set of points
• $\mathcal{B}$ set of blocks
• $I\subseteq \mathcal{P}\times \mathcal{B}$ incidence relation

Define $v=|\mathcal{P}|$ and $b=|\mathcal{B}|$.

De Bruijn–Erdős

If $|\mathcal{B}|⩾2$ for all $B\in \mathcal{B}$, any two distinct points are in precisely one block simultaneously, then $b=1$ or $b⩾v$.

\begin{proof} This proof is given by Conway. Let $r_x$ denote the number of blocks through $x$. For a block $B$, let $k_B$ denote the number of points on $B$.

Suppose that $b⩾2$. If $x\notin B$, then $r_x⩾k_B$. Suppose that $b<v$, then $v-k_B>b-r_x$. We also have

$$\sum _{x\in \mathcal{P}}\sum _{B\in \mathcal{B},x\notin B}\frac{1}{b-r_x}=\sum _{x\in \mathcal{P}}1=v$$

and

$$\sum _{B\in \mathcal{B}}\sum _{x\in \mathcal{P},x\notin B}\frac{1}{v-k_B}=\sum _{b\in \mathcal{B}}1=b.$$

Hence

$$vb=\sum _{x\in \mathcal{P}}\sum _{B\in \mathcal{B},x\notin B}\frac{b}{b-r_x}<\sum _{B\in \mathcal{B}}\sum _{x\in \mathcal{P},x\notin B}\frac{b}{v-k_B}=vb,$$

leading to a contradiction. Therefore, $b⩾v$. \end{proof}

A $t$-$(v,k,\lambda )$ design is a point-block geometry $(\mathcal{P},\mathcal{B})$ where $\mathcal{P}$ is a set of $v$ points and $\mathcal{B}$ is a collection of $k$-subsets of $\mathcal{P}$, with the property that every $t$-subset of $\mathcal{P}$ is contained in exactly $\lambda$ blocks of $\mathcal{B}$.

Link to original

Examples.

• When $\lambda =1$, such design is called “Steiner system” $S(t,k,v)$. In particular, $S(2,3,v)$ is a Steiner triple system. For instance, see here.
• $PG(2,q)$ is a $2$-$(q^2+q+1,q+1,1)$ design
• $AG(2,q)$ is a $2$-$(q^2,q,1)$ design
• $PG(n,q)$ is a $2$-$((q^{n+1}-1)/(q-1),q+1,1)$ design
• Hermitian unital is a $2$-$(q^3+1,q+1,1)$ design. Conversely, such design $2$-$(q^3+1,q+1,1)$ in projective plane is called unital.
• A Hadamard matrix of order $4m$ gives a $2$-$(4m-1,2m-1,m-1)$ design.
  • Let $H$ be a Hadamard matrix of order $4m$ with the first row and the first column all $1$‘s.
  • Let $H^{\prime }$ be the principal sub-matrix of $H$ with the first row and first column deleted.
  • $\mathcal{P}=\{1,\cdots ,4m-1\}$
  • $\mathcal{B}=\{B_1,\cdots ,B_{4m-1}\}$.
  • $B_i:=\{x\in \mathcal{P}:H_{i,x}^{\prime }=1\}$.
• Another example, $S(3,4,10)$:

Theorem

The number of blocks of a $t$-$(v,k,\lambda )$ design is

$$b=\lambda \left(\genfrac{}{}{0ex}{}{v}{t}\right)/\left(\genfrac{}{}{0ex}{}{k}{t}\right).$$

\begin{proof} Count pairs $(T,B)$, where $T\in \left(\genfrac{}{}{0ex}{}{\mathcal{P}}{t}\right)$, $B\in \mathcal{B}$, $T\subseteq B$. \end{proof}

Theorem

Given $i$ with $0⩽i⩽t$, the number of blocks incident with a fixed $i$-subset $I$ of $\mathcal{P}$ is

$$b_i=\lambda \left(\genfrac{}{}{0ex}{}{v-i}{t-i}\right)/\left(\genfrac{}{}{0ex}{}{k-i}{t-i}\right)$$

In the other words, a $t$-design is also a $(t-1)$-design.

\begin{proof} Same as for ^dz2c5i, but with $I\subseteq T\subseteq B$. \end{proof}

Remark. Usually $b_1$ is denoted by $r$, and is called replication number. The following equations is useful for $2$-designs: $bk=vr$ and $\lambda (v-1)=r(k-1)$.

Example. Consider a $2$-$(v,3,1)$ design $b=\lambda \left(\genfrac{}{}{0ex}{}{v}{2}\right)/\left(\genfrac{}{}{0ex}{}{k}{2}\right)=v(v-1)/6$. Then $6\mid v(v-1)$ and so $v\equiv 0,1,3,4(\mathrm{mod}6)$. Moreover, $r=\lambda \left(\genfrac{}{}{0ex}{}{v-1}{t-1}\right)/\left(\genfrac{}{}{0ex}{}{k-1}{t-1}\right)=(v-1)/2$ yields $v\equiv 1,3(\mathrm{mod}6)$.

Remark. These conditions are sufficient. $t$-$(v,k,\lambda )$ designs eventually exist for $t,k,\lambda$ fixed, plus divisible condition from ^25ec95. By Peter Keevash (2014). Explicit construction only for $t⩽5$. For small $v$, the divisibility conditions from the $b_i$‘s are not sufficient. Tits (1964) $S(10,16,72)$ design does not exist.

Theorem

In a non-trivial Steiner system $S(t,k,v)$, we have $v⩾(t+1)(k-t+1)$.

\begin{proof} In a Steiner system $S(t,k,v)$, any two distinct blocks have at most $t-1$ points in common. Let $S$ be a set of $t+1$ points not contained in any block. (Here we use non-triviality) For each $T\in \left(\genfrac{}{}{0ex}{}{S}{t}\right)$, there exists a unique block $B_T$ containing $T$. Each such $B_T$ is incident with $k-t$ points not in $S$. Any point not in $S$ is incident with at most one $B_T$ (as $|B_T\cap B_{T^{\prime }}\cap S|=t-1$). Hence $v⩾(t+1)+(t+1)(k-t)$. \end{proof}

Incidence matrix $N\in {\mathbb{R}}^{v\times b}$, indexed by $\mathcal{P}\times \mathcal{B}$

$$N_{P,B}=\{\begin{array}{ll}1& \text{if }PIB,\\ 0& \text{if }P/IB.\end{array}$$

Then $N^{T}N=rI+(J-I)=(r-\lambda )I+\lambda J$. Moreover, $(N^{T}N{)}_{A,B}=|A\cap B|$. For Hermitian unital, $|A\cap B|\in 0,1$. For $PG(2,q)$, $|A\cap B|\equiv 1$.

Theorem

For a $2$-$(v,k,\lambda )$ design with $b$ blocks and $v>k$, we have $b⩾v$.

\begin{proof} Recall that $\lambda (v-1)=r(k-1)$. So $v>k$, then $r>\lambda$. Thus $N^{T}N=(r-\lambda )I+\lambda J$ has spectrum $(r-\lambda {)}^{v-1}$, $rk$. Thus $\mathrm{rank}(N^{T}N)=v$ as $r\ne \lambda$. Hence $\mathrm{rank}(N)=v$ and so $b⩾v$. \end{proof}

Theorem

If a $2$-$(n,k,\lambda )$ design has $b=v$ and $v$ is even, then $k-\lambda$ is a square.

\begin{proof} Note that $b=v$ yields $r=k$. Then $\det (N{)}^2=\det (N^{T}N)=k^2(k-\lambda {)}^{v-1}$. \end{proof}

Theorem

For $S_{\lambda }(t,k,v)$, $t⩾2s$, $v⩾k+s$, we have $b⩾\left(\genfrac{}{}{0ex}{}{v}{s}\right)$.

\begin{proof} See A course in combinatorics - 2001 - van Lint, Wilson.pdf, theorem 19.8. \end{proof}

Examples of symmetric design:

• Hadamard matrices are $2$-$(4n-1,2n-1,n-1)$ design
• projective planes are $2$-$(n^2+n+1,n+1,1)$ design.

FI thinks that otherwise only a finitely many of symmetric designs is known.

Bruck-Ryser-Chowla

Let $v,k,\lambda$ be positive integer such that $\lambda (v-1)=k(k-1)$, then a symmetric $2$-$(v,k,\lambda )$ design has the following necessary conditions

• $v$ even $⟹$ $k-\lambda$ square
• $v$ odd $⟹$ $z^2=(k-\lambda )x^2+(-1{)}^{(v-1)/2}\lambda y^2$ has a solution $(x,y,z)\in {\mathbb{Z}}^3\setminus \{(0,0,0)\}$.