Combinatorics

11 Combinatorial Designs

Theorem 11.1
#

The preceding algorithm terminates and computes the GCD of \(a\) and \(b\) correctly.

Theorem 11.2
#

Let \(n\) be an integer with \(n \geq 2\) and let \(a\) be a nonzero integer in \(Z_n = \{ O,1 ,\ldots , n - 1\} \). Then \(a\) has a multiplicative inverse in \(Z_n\) if and only if the GCD of \(a\) and \(n\) is \(1\). If \(a\) has a multiplicative inverse, then it is unique.

Corollary 11.3
#

Let \(n\) be a prime number. Then each nonzero integer in \(Z_n\) has a multiplicative inverse.

Theorem 11.4
#

In a BIBD, each variety is contained in

\[ r = \frac{\lambda (v-1)}{k-1} \]

blocks.

Corollary 11.5
#

In a BIBD, we have

\[ bk=vr. \]
Corollary 11.6
#

In a BIBD, we have

\[ \lambda {\lt} r. \]
Theorem 11.7
#

In a BIBD, \(b \geq v.\)

Theorem 11.8
#

Let \(B\) be a subset of \(k {\lt} v\) elements of \(Z_v\) that forms a difference set mod \(v\). Then the blocks developed from \(B\) as a starter block form an SBIBD with index

\[ \lambda = \frac{k(k-1)}{v-1} \]
Theorem 11.9
#

Let \(\mathcal{B}\) be a Steiner triple system with pammeters \(b, v, k = 3, r, \lambda \). Then

\begin{equation} \label{10.4} r = \frac{\lambda (v-1)}{2} \end{equation}
1

and

\begin{equation} \label{10.5} b = \frac{\lambda v(v-1)}{6} \end{equation}
2

If the index is \(\lambda = 1\), then there is a nonnegative integer \(n\) such that \(v = 6n +1\) or \(v = 6n +3\).

Theorem 11.10
#

If there are Steiner triple systems of index \(\lambda = 1\) with \(v\) and \(w\) varieties, respectively, then there is a Steiner triple system of index \(\lambda = 1\) with \(vw\) varieties.

Theorem 11.11
#

Let \(n\) be a positive integer. Let \(A\) be the \(n\)-by-\(n\) array whose entry \(a_{ij}\) in row \(i\) and column \(j\) is

\[ a_{i j}=i+j(\text{addition mod} \hspace{0.5em} n),(i, j=0,1, \ldots , n-1) \]

Then \(A\) is a Latin square of order \(n\) based on \(Z_n\).

Theorem 11.12
#

Let \(n\) be a positive integer and let \(r\) be a nonzero integer in \(Z_n\) such that the GCD of rand \(n\) is \(1\). Let \(A\) be the \(n\)-by-\(n\) array whose entry \(a_{ij}\) in row \(i\) and column \(j\) is

\[ a_{i j}=r \times i+j(\text{addition mod} \hspace{0.5em} n),(i, j=0,1, \ldots , n-1) \]

Then \(A\) is a Latin square of order \(n\) based on \(Z_n\).

Theorem 11.13
#

Let \(n\) be a prime number. Then \(L_n^1, L_n^2, \ldots , L_n^{n-1}\) are \(n - 1\) MOLS of order \(n\).

Theorem 11.14
#

Let \(n = p^k\) be an integer that is a power of a prime number \(p\). Then there exist \(n - 1\) MOLS of order \(n\). In fact, the \(n - 1\) Latin squares (10.12) of order \(n\) constructed from a finite field with \(n = p^k\) elements are \(n - 1\) MOLS of order \(n\).

Theorem 11.15
#

Let \(n \geq 2\) be an integer, and let \(A_1, A_2,\ldots , A_k\) be \(k\) MOLS of order \(n\). Then \(k \leq n - 1\); that is, the largest number of MOLS of order \(n\) is at most \(n - 1\).

Theorem 11.16
#

\(N(n) \geq 2\) for each odd integer \(n\).

Theorem 11.17
#

If there is a pair of MOLS of order \(m\) and there is a pair of MOLS of order \(k\), then there is a pair of MOLS of order \(mk\). More generally,

\[ N(mk) \geq \min \{ N(m), N(k)\} \]
Theorem 11.18
#

Let \(n \geq 2\) be an integer and let

\[ n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]

be the factorization of \(n\) into distinct prime numbers \(p_1, p_2, \ldots , p_k\). Then

\[ N(n) \geq \min \left\{ p_i^{e_2}-1: i=1,2, \ldots , k\right\} \]
Corollary 11.19
#

Let \(n \geq 2\) be an integer that is not twice an odd number. Then there exists a pair of orthogonal Latin squares of order \(n\).

Theorem 11.20
#

Let \(n \geq 2\) be an integer. If there exist \(n-1\) MOLS of order \(n\), then there exists a resolvable BIBD with parameters

\begin{equation} \label{10.18} b=n^2+n, v=n^2, k=n^{\prime }, r=n+1, \lambda =1 \end{equation}
3

Conversely, if there exists a resolvable BIBD with parameters (10.18), then there exist \(n-1\) MOLS of order \(n\).

Theorem 11.21
#

Let \(L\) be an \(m\)-by-\(n\) Latin rectangle based on \(Z_n\) with \(m {\lt} n\). Then \(L\) has a completion.

Theorem 11.22
#

Let \(L\) be a semi-Latin square of order \(n\) and index \(m\), where \(m {\lt} n\). Then \(L\) has a completion.