1. 引言
设和t是给定的正整数,G-设计(记为)是一个三元组(X, A, B),其中X是一个元点集,A构成X的一个划分,B是X的一些子集组成的一个子集族,X的元素叫点,A的元素叫组,B的元素叫区组,满足(1)对任意,都有;(2)对任意,都有;(3)对任意与任意,都有;(4)对于X中每个t元子集T与任意,如果,则T恰好包含于B中个区组。时,记为。
当时,G-设计就是大家熟知的可分组设计或GD设计(参见[1] )。当时,G-设计是柄为0的烛台型四元系,而烛台型四元系在四元系中起到相当重要的作用(参见[2] )。Mills [3] [4] ,Hartman [5] [6] 研究了,得到了一些结论。当时,易知存在的充分必要条件是: (参见[4] )。本文讨论当时,的存在性。我们给出存在的充分必要条件是:。
文中用到的组合设计及图论方面的名词术语均参照著作[1] 和[7] 。
2. 预备知识
定理2.1存在的必要条件是:。
证明:中有个点,不同的三元点集共有个,其中能出现在区组中的有,而一个区组含有四个三元集,一个三元集可出现在个区组中,所以,中的区组数为,因而,。再设是设计中给定的点,能和组成三元集的点对共有个,其中能出现在区组中的有个,且每个三元集可出现在个区组中,而一个区组中能和组成三元集的点对有三个,所以,。综上两点,可得存在的必要条件是。
上述存在的必要条件可分类等价于以下四种情形
1)且或
2)且或
3)且或
4)且。
为证存在的充分性,我们需要图1-因子分解的有关知识。记G是具有个g点的图,其点集为。设,图G的边的差定义为和中小的一个。我们记图G的边的差为或,也即是
。
对于任何一个子集(表示不大于的最大整数),我们定义是一个图,其点集为,边集为,即包含所有差属于的边。
图的一个子图如果包含了的全部点,则为的生成子图。如果图的一个生成子图是1-正则的,则称是的1-因子。如果图的边集可表示为它的某些1-因子的并,则称存在的1-因子分解,或称可1-因子化。下面的引理来自Stern和Lenz [8] ,我们在第3节的证明中将会用到,其中表示和的最大公约数。
引理2.2 (Stern和Lenz)如果包含一个元素使得是偶数,则图存在1-因子分解。
3. 主要结论
引理3.1如果存在,则对于任意正整数,存在。
证明:将的每个区组重复s倍,即得。
由引理2.1结合引理3.1,为证主要结论,我们只需考虑以下四种情形
1)且;
2)且;
3)且;
引理3.2当时,存在。
证明:设,记所需设计的点集,组A:{: }。
区组B:{,,, }
(,,,);
{,,, }
(由引理2.2,图存在1-因子分解,记是的1-因子分解,,)。
引理3.3当时,存在。
(,,,)重复4次;
(,,)重复2次;
{,,, }(,);
{,,, }(,,)。
引理3.4当时,存在。
区组B:{,,, } (,,,);
{,,, } (,,);
{,,, } (,)。
引理3.5当时,存在。
(,,,)重复2次;
{,,, }(,,);
{,,, }(,,)
{,,, }(,)
定理3.6当时,存在。
证明:由引理3.2~3.5,结合引理3.1,可得存在的充分条件。
结合引理2.1和定理3.6,我们得到本文的主要结论。
定理3.7存在的充分必要条件是。
基金项目
国家自然科学基金项目(11171248和11371207)。
参考文献