Covering triples by quadruples: An asymptotic solution
Covering triples by quadruples: An asymptotic solution
复制标题
DOI：
10.1016/0097-3165(86)90119-6
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
Alan Hartman;W. Mills;R. Mullin
中科院分区：
文献类型：
--
作者：
Alan Hartman;W. Mills;R. Mullin
Abstract Let C (3, 4, n) be the minimum number of four-element subsets (called blocks) of an n-element set, X, such that each three-element subset of X is contained in at least one block. Let L (3, 4, n)=⌜ n 4⌜ n− 1 3⌜ n− 2 2⌝⌝⌝. Schoenheim has shown that C (3, 4, n)⩾ L (3, 4, n). The construction of Steiner quadruple systems of all orders n≡ 2 or 4 (mod 6) by Hanani (Canad. J. Math. 12 (1960), 145–157) can be used to show that C (3, 4, n)= L (3, 4, n) for all n≡ 2, 3, 4 or 5 (od 6) and all n≡ 1 (mod 12). The case n≡ 7 (mod 12) is made more difficult by the fact that C (3, 4, 7)= L (3, 4, 7)+ 1 and until recently no other value for C (3, 4, n) with n≡ 7 (mod 12) was known. In 1980 Mills showed by construction that C (3, 4, 499)= L (3, 4, 499). We use this construction and some recursive techniques to show that C (3, 4, n)= L (3, 4, n) for all n⩾ 52423. We also show that if C (3, 4, n)= L (3, 4, n) for n= 31, 43, 55 and if a certain configuration on 54 points exists then C (3, 4, n)= L (3, 4, n) for all n≠ 7 with the possible exceptions of n= 19 and n= 67. If we assume only C (3, 4, n)= L (3, 4, n) for n= 31 and 43 we can deduce that C (3, 4, n)= L (3, 4, n) for all n≠ 7 with the possible exceptions of n ϵ {19, 55, 67, 173, 487}.
