An Open Problem in Embedding

Sarvate, Dinesh G.; Zhang, Li

doi:10.61091/jcmcc121-05

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 121
Pages: 53-57

Research article

An Open Problem in Embedding

^¹, ^²

¹College of Charleston, Dept. of Math., Charleston, SC, 29424

²The Citadel, Dept. of Math., Charleston, SC, 29409

Published: 30/06/2024

Copyright Link
License

Abstract

We propose and study the problem of finding the smallest nonnegative integer $s$ such that a GDD $(m, n, 3; 0, λ)$ can be embedded into a BIBD $(m n + s, 3, λ)$ . We find the values of $s$ for all cases except for the case where $n \equiv 5 (\mod 6)$ and $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$ , which remains as an open problem.

Keywords: k-dyck paths, Bijections, Generating Functions

1. Folklore Results about $k$ -Dyck Paths

Balanced incomplete block designs (BIBDs) and group divisible designs (GDDs) have been studied for their usefulness in statistics and for their universal application to constructions of new designs. Certain difficulties are present especially when the number of groups is smaller than the block size.

Definition 1. A balanced incomplete block design, BIBD $(v, b, r, k, λ)$ , is a collection of $b$ $k$ -subsets $($ called blocks $)$ of a $v$ -set $V$ , such that each element appears in exactly $r$ blocks, every pair of distinct elements of $V$ occurs in $λ$ blocks and $k < v .$ A BIBD $(v, b, r, k, λ)$ is also written as a BIBD $(v, k, λ)$ . The parameter $λ$ is called the index of the design.

A BIBD $(v, 3, 1)$ is also called a Steiner Triple System(STS( $v$ )), and it is known that a STS( $v$ ) exists iff $v \equiv 1, 3 (\mod 6)$ . For general $v$ and $λ$ , we have the following.

A BIBD $(v, 3, λ)$ where $λ \equiv 1, 5 (\mod 6)$ exists if $v \equiv 1, 3 (\mod 6)$ .
A BIBD $(v, 3, λ)$ where $λ \equiv 2, 4 (\mod 6)$ exists if $v \equiv 0, 1 (\mod 3)$ .
A BIBD $(v, 3, λ)$ where $λ \equiv 3 (\mod 6)$ exists if $v \equiv 1 (\mod 2)$ .
A BIBD $(v, 3, λ)$ where $λ \equiv 0 (\mod 6)$ exists if $v \geq 3$ .

Definition 2. A group divisible design, GDD $(m, n, k; λ_{1}, λ_{2})$ , is a collection of $k$ -element subsets of a $v$ -set $V$ called blocks which satisfies the following properties: the $v = m n$ elements of $V$ are partitioned into $m$ subsets $($ called groups $)$ of size $n$ each; each point of $V$ appears in $r = \frac{λ_{1} (n - 1) + λ_{2} n (m - 1)}{k - 1}$ $($ called the replication number $)$ of the $b = \frac{m n r}{k}$ blocks; points within the same group are called first associates of each other and appear together in $λ_{1}$ blocks; any two points not in the same group are called second associates of each other and appear together in $λ_{2}$ blocks, where $λ_{1}$ and $λ_{2}$ are called indices of the GDD.

Example 1. A GDD $(m = 3, n = 2, k = 3; λ_{1} = 0, λ_{2} = 3)$ on $V = {1, 2, 3, 4, 5, 6}$ is as follows. Partitioning $V$ into three groups $G_{1} = {1, 2}$ , $G_{2} = {3, 4}$ and $G_{3} = {5, 6}$ , and the 12 blocks are $\begin{array}{ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc} 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 1 & 2 & 2 \\ 3 & 3 & 4 & 4 & 3 & 3 & 4 & 4 & 3 & 4 & 3 & 4 \\ 5 & 6 & 5 & 6 & 5 & 6 & 5 & 6 & 5 & 6 & 6 & 5 \end{array}$

Definition 3. A Partial Steiner Triple System on $v$ points, PSTS $(v)$ , is a pair $(V, X)$ , where $V$ denotes a set of $v$ elements and $X$ denotes a set of $b$ triples from $V$ , such that $| B \cap B^{'} | \leq 1$ , when $B, B^{'} \in X$ and $B \neq B^{'}$ .

It is well known that every PSTS $(u)$ has an embedding in an STS $(v)$ for each $v \equiv 1, 3 (\mod 6)$ satisfying $v \geq 2 u + 1$ [1]. It is also known that this result is best possible in the sense that, for each $u \geq 9$ , there exists an PSTS $(u)$ that does not have an embedding in an STS $(v)$ for any $v < 2 u + 1$ . Studies in [3] have shown that some PSTS $(u)$ s do have embeddings in a STS $(v)$ for $v < 2 u + 1$ . In this paper, we are studying such an embedding where the partial triple system is a GDD $(m, n, 3; 0, λ)$ (where $u = m n$ ). As a GDD structure is more specific, we can reduce the bound on $v$ significantly and in fact get exact value. For example, when $λ = 1$ , if $n \equiv 1, 3 (\mod 6)$ , then $v = u = m n$ ; if $n \equiv 0, 2 (\mod 6)$ , then $v = u + 1 = m n + 1$ . The challenge arises when $n \equiv 5 (\mod 6)$ . In other words, we study the problem to find the smallest nonnegative integer $s$ such that a GDD $(m, n, 3; 0, λ)$ can be embedded into a BIBD $(m n + s, 3, λ)$ in this paper.

Example 2. This example shows that the blocks of a GDD $(m = 3, n = 2, k = 3; λ_{1} = 0, λ_{2} = 3)$ is embedded in a BIBD $(v = 7 = m \times n + 1, k = 3, λ = λ_{2} = 3)$ , where the smallest nonnegative integer $s$ is 1. A BIBD $(7, 3, 3)$ on $V \cup {a}$ has 21 blocks where the first 12 blocks are from the GDD $(2, 3, 3; 0, 3)$ on $V = {1, 2, 3, 4, 5, 6}$ , $G_{1} = {1, 2}$ , $G_{2} = {3, 4}$ and $G_{3} = {5, 6}$ in Example 1.

$\begin{array}{cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc} 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 1 & 2 & 2 & 1 & 1 & 1 & 3 & 3 & 3 & 5 & 5 & 5 \\ 3 & 3 & 4 & 4 & 3 & 3 & 4 & 4 & 3 & 4 & 3 & 4 & 2 & 2 & 2 & 4 & 4 & 4 & 6 & 6 & 6 \\ 5 & 6 & 5 & 6 & 5 & 6 & 5 & 6 & 5 & 6 & 6 & 5 & a & a & a & a & a & a & a & a & a \end{array}$

Notice that if a BIBD $(n, k, λ)$ exists, then we can combine the blocks of a BIBD $(n, k, λ)$ on each of the $m$ groups with a GDD $(m, n, k; 0, λ)$ to have a BIBD $(m n, k, λ)$ . Hence, we have the following observation.

Observation 1. A GDD $(m, n, k; 0, λ)$ can be embedded into a BIBD $(m n, k, λ)$ if a BIBD $(n, k, λ)$ exists.

Corollary 1. Necessary conditions are sufficient for embedding a GDD $(m, n, 3; 0, λ)$ into a BIBD $(m n, 3, λ)$ where the smallest $s$ equals 0 for $n \equiv 1, 3 (\mod 6)$ for any $λ \geq 1$ .

Proof. If $n = 1$ , a GDD $(m, 1, 3; 0, λ)$ is a BIBD $(m, 3, λ)$ . For $n \geq 3$ , a BIBD $(n, 3, λ)$ exists if $n \equiv 1, 3 (\mod 6)$ . By Observation 1, a GDD $(m, n, 3;$ $0, λ)$ can be embedded in a BIBD $(m n, 3, λ)$ where the smallest $s$ equals 0.

Lemma 1. [2] The necessary and sufficient conditions of the existence of a GDD $(m, n, 3; 0, λ)$ are $m \geq 3$ , $λ (m - 1) n \equiv 0 (\mod 2)$ and $λ m (m - 1) n^{2} \equiv 0 (\mod 6)$ .

Theorem 2. A GDD $(m, n, k; 0, λ)$ can be embedded into a BIBD $(m n + 1, k, λ)$ if a BIBD $(n + 1, k, λ)$ exists.

Proof. Combining the blocks of a GDD $(m, n, k; 0, λ)$ , the blocks of a BIBD $(n + 1, k, λ)$ on each group $G_{i} \cup {\infty}$ ( $i = 1, \dots, m$ ) gives us a BIBD $(m n + 1, k, λ)$ .

Corollary 2. Necessary conditions are sufficient for embedding a GDD $(m, n, 3; 0, λ)$ into a BIBD $(m n + 1, 3, λ)$ where the smallest $s$ equals 1 for $n \equiv 0, 2 (\mod 6)$ for any $λ \geq 1$ .

2. $λ \equiv 0 (\mod 6)$

If $λ \equiv 0 (\mod 6)$ , the necessary condition for the existence of a GDD $(m,$ $n, 3; 0, λ)$ by Lemma 1 is $m \geq 3$ .

Lemma 2. The necessary condition $m \geq 3$ is sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n, 3, λ)$ (except for $n = 2$ ) and in a BIBD $(m n + 1, 3, λ)$ , respectively, where $λ \equiv 0 (\mod 6)$ .

Proof. If $n = 1$ , a GDD $(m, 1, 3; 0, λ)$ is a BIBD $(m, 3, λ)$ . For $n \geq 3$ , a BIBD $(n, 3, λ)$ exists if $λ \equiv 0 (\mod 6)$ , so a GDD $(m, n, 3; 0, λ)$ can be embedded in a BIBD $(m n, 3, λ)$ by Observation 1. Therefore, the necessary condition $m \geq 3$ is sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n, 3, λ)$ (except for $n = 2$ ) when $λ \equiv 0 (\mod 6)$ , i.e., $s = 0$ .

Furthermore, for $n \geq 2$ , combining the blocks of a BIBD $(n + 1, 3, λ)$ on elements in ${a} \cup G_{i}$ ( $i = 1, \dots, m$ and $a \notin G_{i}$ ) and the blocks of a GDD $(m, n, 3; 0, λ)$ (same idea as illustrated in Example 2), we have a BIBD $(m n + 1, 3, λ)$ . Specifically, this implies that if $n = 2$ , then $s = 1$ .

3. $λ \equiv 3 (\mod 6)$

If $λ \equiv 3 (\mod 6)$ , the necessary conditions for the existence of a GDD $(m, n, 3; 0, λ)$ by Lemma 1 are

$n$ is even and $m \geq 3$ .
$n$ is odd and $m$ is odd and $m \geq 3$ .

Using the same proof as in Lemma 2 (the second part of the proof), we have the following lemma.

Lemma 3. The necessary conditions, $n$ is even and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n + 1, 3, λ)$ where $λ \equiv 3 (\mod 6)$ .

Note that since a BIBD $(m n, 3, λ)$ does not exist if $λ \equiv 3 (\mod 6)$ and $n$ is even, $s = 1$ . Also, since a BIBD $(n, 3, λ)$ exists if $λ \equiv 3 (\mod 6)$ and $n$ is odd, we have the following lemma by Observation 1.

Lemma 4. The necessary conditions, $n$ is odd and $m$ is odd and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n, 3, λ)$ where $λ \equiv 3 (\mod 6)$ .

4. $λ \equiv 2, 4 (\mod 6)$

If $λ \equiv 2, 4 (\mod 6)$ , the necessary conditions for the existence of a GDD $(m, n, 3; 0, λ)$ by Lemma 1 are

$n \equiv 0 (\mod 3)$ and $m \geq 3$ .
$n \equiv 1, 2 (\mod 3)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ .

By Observation 1, we have the following lemma.

Lemma 5. The necessary conditions, $n \equiv 0 (\mod 3)$ and $m \geq 3$ , or $n \equiv 1 (\mod 3)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n, 3, λ)$ where $λ \equiv 2, 4 (\mod 6)$ .

Use the same proof as in Lemma 2, we have the following lemma.

Lemma 6. The necessary conditions, $n \equiv 2 (\mod 3)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n + 1, 3, λ)$ where $λ \equiv 2, 4 (\mod 6)$ .

5. $λ \equiv 1, 5 (\mod 6)$

If $λ \equiv 1, 5 (\mod 6)$ , the necessary conditions for the existence of a GDD $(m, n, 3; 0, λ)$ by Lemma 1 are

For $n \equiv 0 (\mod 6)$ , $m \geq 3$ .
For $n \equiv 2, 4 (\mod 6)$ , $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ .
For $n \equiv 1, 5 (\mod 6)$ , $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$ .
For $n \equiv 3 (\mod 6)$ , $m$ is odd and $m \geq 3$ .

By Corollary 1, we have the following Lemmas 7 and 8.

Lemma 7. The necessary conditions, $n \equiv 0 (\mod 6)$ and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n + 1, 3, λ)$ where $λ \equiv 1, 5 (\mod 6)$ .

Lemma 8. The necessary conditions, $n \equiv 2 (\mod 6)$ , $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n + 1, 3, λ)$ where $λ \equiv 1, 5 (\mod 6)$ .

Lemma 9. A GDD $(m, n, 3; 0, λ)$ can be embedded in a BIBD $(m n + 3, 3, λ)$ if $n \equiv 4 (\mod 6)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ . Furthermore, $s = 3$ is the smallest nonnegative integer if $λ \equiv 1, 5 (\mod 6)$ .

Proof. If $n \equiv 4 (\mod 6)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$ , a GDD $(m, n, 3; 0, λ)$ exists. A BIBD $(n + 3, 3, 1)$ exists since $n + 3 \equiv 1 (\mod 6)$ . Let $X$ be the collection of the blocks of a GDD $(m, n, 3; 0, λ)$ on $m n$ elements where each group $G_{i}$ ( $i = 1, \dots, m$ ) has group size $n$ . Let $Y_{i}$ be the blocks of a BIBD $(n + 3, 3, 1)$ on the elements in ${a, b, c} \cup G_{i}$ ( $i = 1, \dots, m$ ) where one block is ${a, b, c}$ (this can be done by relabelling the elements). The blocks of $X$ together with $λ$ copies of $⋃_{i = 1}^{m} (Y_{i} ∖ {a, b, c})$ and $λ$ copies of ${a, b, c}$ forms a BIBD $(m n + 3, 3, λ)$ .

Furthermore, if $λ \equiv 1, 5 (\mod 6)$ , a BIBD $(m n, 3, λ)$ does not exist, and a BIBD $(m n + 2, 3, λ)$ does not exist, and a GDD $(m, n, 3; 0, λ)$ cannot be embedded in a BIBD $(m n + 1, 3, λ)$ by Theorem 2 since a BIBD $(n + 1, 3, λ)$ does not exist, $s = 3$ is the smallest nonnegative integer.

Example 3. Figure 1 shows the 35 blocks of a BIBD $(15, 3, 1)$ where a GDD $(3, 4, 3; 0, 1)$ is embedded in the BIBD $(12 + 3, 3, 1)$ . $G_{1} = {1, 2, 3, 4}$ , $G_{2} = {5, 6, 7, 8}$ , and $G_{3} = {9, 10, 11, 12}$ . As stated in the proof of Lemma 9, the first 16 blocks are the blocks of a GDD $(3, 4, 3; 0, 1)$ , and the next 7 blocks are from a BIBD $(7, 3, 1)$ on ${a, b, c} \cup G_{1}$ . The last 12 blocks are from a BIBD $(7, 3, 1)$ on ${a, b, c} \cup G_{2}$ and on ${a, b, c} \cup G_{3}$ , respectively, where ${a, b, c}$ is removed since it should only be counted once.

Figure 1: A GDD $(3, 4, 3; 0, 1)$ is Embedded in a BIBD $(15, 3, 1)$

By Corollary 1, we have the following.

Corollary 3. The necessary conditions, $n \equiv 1 (\mod 6)$ and $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$ , or $n \equiv 3 (\mod 6)$ , $m$ is odd and $m \geq 3$ are sufficient to embed a GDD $(m, n, 3; 0, λ)$ in a BIBD $(m n, 3, λ)$ where $λ \equiv 1, 5 (\mod 6)$ .

6. Summary

In this paper we proposed a problem to find the smallest nonnegative integer $s$ such that a GDD $(m, n, k; 0, λ)$ can be embedded into a BIBD $(m n + s, 3, λ)$ . We found the values of $s$ for all cases except for the case where $λ \equiv 1, 5 (\mod 6)$ , $n \equiv 5 (\mod 6)$ , $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$ , which remains as an open problem. As mentioned earlier, every PSTS $(u)$ has an embedding in an STS $(v)$ for each $v \equiv 1, 3 (\mod 6)$ satisfying $v \geq 2 u + 1$ [1], hence when $λ \equiv 1, 5 (\mod 6)$ , $s \leq m n + 1$ for $n \equiv 5 (\mod 6)$ and $m \equiv 3 (\mod 6)$ , and $s \leq m n + 3$ for $n \equiv 5 (\mod 6)$ and $m \equiv 1 (\mod 6)$ . Our guess is in these cases $s = m n + 1$ and $s = m n + 3$ , respectively.

A summary of finding the smallest nonnegative integer $s$ such that a GDD $(m, n, 3; 0, λ)$ can be embedded into a BIBD $(m n + s, 3, λ)$ is in Table 1 as follows.

Table 1: Necessary Conditions and the Smallest Nonnegative Integer $s$
$λ$	$m, n$	Necessary Conditions Sufficient?	$s$
$0 (\mod 6)$	$m \geq 3$	Yes	$0$ if $n = 1$ or $n \geq 3$
			$1$ if $n = 2$
$3 (\mod 6)$	$n$ even and $m \geq 3$	Yes	$1$
	$m, n$ both odd and $m \geq 3$	Yes	0
$2, 4 (\mod 6)$	$n \equiv 0 (\mod 3)$ and $m \geq 3$	Yes	$0$
	$n \equiv 1 (\mod 3)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$	Yes	$0$
	$n \equiv 2 (\mod 3)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$	Yes	1
$1, 5 (\mod 6)$	$n \equiv 0 (\mod 6)$ and $m \geq 3$	Yes	$1$
	$n \equiv 2 (\mod 6)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$	Yes	$1$
	$n \equiv 4 (\mod 6)$ and $m \equiv 0, 1 (\mod 3)$ and $m \geq 3$	Yes	$3$
	$n \equiv 1 (\mod 6)$ and $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$	Yes	0
	$n \equiv 3 (\mod 6)$ and $m$ odd and $m \geq 3$	Yes	0
	$n \equiv 5 (\mod 6)$ and $m \equiv 1, 3 (\mod 6)$ and $m \geq 3$	Yes	Open

Acknowledgment

Dinesh Sarvate wishes to thank Professors Liz Jurisich and Bob Mignone for their continued support through departmental research funding. Li Zhang thanks The Citadel Foundation for its support.

Conflict of interest

The authors declare no conflict of interest.

References:

Bryant, D. and Horsley, D., 2009. A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems. Journal of Combinatorial Designs, 17(1), pp.63-89.
Colbourn, C. J. and Dinitz, D. H., 2007. Handbook of Combinatorial Designs (2nd edition). Chapman and Hall, CRC Press, Boca Raton.
Horsley, D., 2014. Small embeddings of partial Steiner triple systems. Journal of Combinatorial Designs, 22(8), pp.343-365.

[1] Bryant, D. and Horsley, D., 2009. A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems. Journal of Combinatorial Designs, 17(1), pp.63-89.

[2] Colbourn, C. J. and Dinitz, D. H., 2007. Handbook of Combinatorial Designs (2nd edition). Chapman and Hall, CRC Press, Boca Raton.

[3] Horsley, D., 2014. Small embeddings of partial Steiner triple systems. Journal of Combinatorial Designs, 22(8), pp.343-365.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

An Open Problem in Embedding

Abstract

1. Folklore Results about $k$ -Dyck Paths

2. $λ \equiv 0 (\mod 6)$

3. $λ \equiv 3 (\mod 6)$

4. $λ \equiv 2, 4 (\mod 6)$

5. $λ \equiv 1, 5 (\mod 6)$

6. Summary

Acknowledgment

Conflict of interest

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

An Open Problem in Embedding

Abstract

1. Folklore Results about k-Dyck Paths

2. λ≡0(mod6)

3. λ≡3(mod6)

4. λ≡2,4(mod6)

5. λ≡1,5(mod6)

6. Summary

Acknowledgment

Conflict of interest

References:

Information

Guidelines

CP Initiatives

Follow CP

1. Folklore Results about $k$ -Dyck Paths

2. $λ \equiv 0 (\mod 6)$

3. $λ \equiv 3 (\mod 6)$

4. $λ \equiv 2, 4 (\mod 6)$

5. $λ \equiv 1, 5 (\mod 6)$