Abstract
A transversal cover is a set of gk points in k disjoint groups of size g and a collection of b transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. A central question is to determine, for given g, the minimum possible b for fixed k, or, alternatively, the maximum k for fixed b. The case g=2 was investigated and completely solved by Sperner sperner:28, Rényi renyi:71, Katona katona:73, and Kleitman and Spencer kleitman:73. For arbitrary g, asymptotic results are known but little is understood for small values of k. Constructions exist but these only produce upper bounds on b. The present article is concerned with lower bounds on b. We develop three general lower bounds on b for fixedg and k. The first one is proved using one of the principal constructions brett:97a, the second comes from the study of intersecting set-systems, and the third is shown by a set packing argument. In addition, we investigate upper bounds on k for small fixed b. This proves useful to reduce or eliminate the gap between lower and upper bounds on b for some transversal covers with small k.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton, The combinatorial design approach to automatic test generation, IEEE Software, Vol. 13, No.5 (1996) pp. 83-88.
P. Erdös, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, Vol. 12 (1961) pp. 313-318.
Z. Füredi, Matchings and cover in hypergraphs, Graphs Combin., Vol. 4 (1988) pp. 115-206.
L. Gargano, J. Körner, and U. Vaccaro, Qualitative independence and Sperner problems for directed graphs, J. Combin. Theory. Ser. A, Vol. 61 (1992) pp. 173-192.
L. Gargano, J. Körner, and U. Vaccaro, Sperner capacities, Graphs Combin., Vol. 9 (1993) pp. 31-46.
L. Gargano, J. Körner, and U. Vaccaro, Capacities: From information theory to extremal set theory, J. Combin. Theory. Ser. A, Vol. 68 (1994) pp. 296-316.
F. Jaeger and C. Payan, Nombre maximal d'arétes d'un hypergraphe critique de rang h, C. R. Acad. Sci. Paris, Vol. 273 (1971) pp. 221-223.
G. O. H. Katona, Two applications (for search theory and truth functions) of Sperner type theorems, Period. Math. Hungar., Vol. 3 (1973) pp. 19-26.
G. O. H. Katona, Solution of a problem of Ehrenfeucht and Mycielski, J. Combin. Theory. Ser. A, Vol. 17 (1974) pp. 265-266.
D. J. Kleitman and J. Spencer, Families of k-independent sets, Discrete Math., Vol. 6 (1973) pp. 255-262.
J. Körner and M. Lucertini, Compressing inconsistent data, IEEE Trans. Inform. Theory, Vol. 40, No.3 (1994) pp. 706-715.
B. Stevens, A. Ling and E. Mendelsohn, A direct construction of transversal covers using group divisible designs, in preparation.
S. Poljak and Z. Tuza, On the maximum number of qualitatively independent partitions, J. Combin. Theory. Ser. A, Vol. 51 (1989) pp. 111-116.
A. Rényi, Foundations of Probability, Wiley, New York (1971).
N. J. A. Sloane, Covering arrays and intersecting codes, J. Combin. Des., Vol. 1 (1993) pp. 51-63.
E. Sperner, Ein satz Über untermengen einer endlichen menge, Math Z., Vol. 27 (1928) pp. 544-548.
B. Stevens and E. Mendelsohn, New recursive methods for transversal covers, to appear in J. Combin. Des.
A. W. Williams and R. L. Probert, A practical strategy for testing pair-wise convergence of network interfaces, Proc. of the 7th International Symposium on Software Reliability Engineering, (1996) pp. 246-254.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Stevens, B., Moura, L. & Mendelsohn, E. Lower Bounds for Transversal Covers. Designs, Codes and Cryptography 15, 279–299 (1998). https://doi.org/10.1023/A:1008329410829
Issue Date:
DOI: https://doi.org/10.1023/A:1008329410829