On covering a product of sets with products of their subsets

A. M. Odlyzko

doi:10.1016/0012-365X(73)90130-1

On covering a product of sets with products of their subsets

A. M. Odlyzko

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Suppose that S₁,...,S_N are collections of subsets of X₁,...,X_N, respectively, such that n_i subsets belonging to S_i, and no fewer, cover X_i for all i. the main result of this paper is that to cover X₁ x...x X_N requires no fewer than σ^N_i=1 (n_i-1) + 1 and no more than Π^N_i=1n_i subsets of the form A₁ x...x A_N, where A_i∈S₁ for all i. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.

Original language	English (US)
Pages (from-to)	373-380
Number of pages	8
Journal	Discrete Mathematics
Volume	5
Issue number	4
DOIs	https://doi.org/10.1016/0012-365X(73)90130-1
State	Published - Aug 1973
Externally published	Yes

Bibliographical note

Funding Information:
* 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. ** Original version received 15 November 1971.

Publisher link

10.1016/0012-365X(73)90130-1

Find It

Find It at U of M Libraries

Cite this

@article{0ab520cac54c4c13b31c5efd1125462c,

title = "On covering a product of sets with products of their subsets",

abstract = "Suppose that S1,...,SN are collections of subsets of X1,...,XN, respectively, such that ni subsets belonging to Si, and no fewer, cover Xi for all i. the main result of this paper is that to cover X1 x...x XN requires no fewer than σNi=1 (ni-1) + 1 and no more than ΠNi=1ni subsets of the form A1 x...x AN, where Ai∈S1 for all i. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.",

author = "Odlyzko, \{A. M.\}",

note = "Funding Information: * 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. ** Original version received 15 November 1971.",

year = "1973",

month = aug,

doi = "10.1016/0012-365X(73)90130-1",

language = "English (US)",

volume = "5",

pages = "373--380",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - On covering a product of sets with products of their subsets

AU - Odlyzko, A. M.

N1 - Funding Information: * 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. ** Original version received 15 November 1971.

PY - 1973/8

Y1 - 1973/8

N2 - Suppose that S1,...,SN are collections of subsets of X1,...,XN, respectively, such that ni subsets belonging to Si, and no fewer, cover Xi for all i. the main result of this paper is that to cover X1 x...x XN requires no fewer than σNi=1 (ni-1) + 1 and no more than ΠNi=1ni subsets of the form A1 x...x AN, where Ai∈S1 for all i. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.

AB - Suppose that S1,...,SN are collections of subsets of X1,...,XN, respectively, such that ni subsets belonging to Si, and no fewer, cover Xi for all i. the main result of this paper is that to cover X1 x...x XN requires no fewer than σNi=1 (ni-1) + 1 and no more than ΠNi=1ni subsets of the form A1 x...x AN, where Ai∈S1 for all i. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.

UR - https://www.scopus.com/pages/publications/2442634303

UR - https://www.scopus.com/pages/publications/2442634303#tab=citedBy

U2 - 10.1016/0012-365X(73)90130-1

DO - 10.1016/0012-365X(73)90130-1

M3 - Article

AN - SCOPUS:2442634303

SN - 0012-365X

VL - 5

SP - 373

EP - 380

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

ER -

On covering a product of sets with products of their subsets

Abstract

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this