On covering a product of sets with products of their subsets

✍ Scribed by A.M. Odlyzko

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 599 KB
• Volume: 5
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(73)90130-1

✦ Synopsis

• 1 and no more than for all i. Moreover, these bounds cannot "t be improved. Identical bounds for the spanning number ' f :i no:mal product of graphs are also obtained.

.

Let S be a collection of subsets of a set X such that their union is X. Define c(X;S), the covering number of X wi;h rLhspect to S, to be the minimal number of elements of S whose union 14 X. We will always assume that this number exists. If S,, . . . . SN are collect%,ns of subsets of Xl , . . ..XN. respectively, define a colk.:tion S, >/, ,.. X SN of subsets of the Cartesian product X, X . . . X XN by SIX . ..XS.=i~lX...XA,IAiESi,i=l,...,N). This gaper is ccncerned with the dependence of c(X~ X . . . X XN ; Sl X . . . X SN) on the C(Xi;Si). It is easy to see that c(Xr x . . . x X,,;S, x . . . Moreover, this bound cannot be improved, since equality holds when-* This paper presents the results of one phase of research carria,d oui at :he Jet Propulsion Laboratory, California Institute of Technology, under Contrxt No. NAS 7-100, sponsored by the National Aeronautics a1.d Space Administration.