article

On covering a product of sets with products of their subsets

Author:

A. M. OdlyzkoAuthors Info & Claims

Discrete Mathematics, Volume 5, Issue 4

Pages 373 - 380

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

Published: 01 August 1973 Publication History

Abstract

Suppose that S"1,...,S"N are collections of subsets of X"1,...,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"1 x...x X"N requires no fewer than @s^N"i"="1 (n"i-1) + 1 and no more than @P^N"i"="1n"i subsets of the form A"1 x...x A"N, where A"i@?S"1foralli. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.

References

[1]

Berge, C., The theory of graphs and its applications. 1962. Wiley, New York.

Google Scholar

[2]

Erdös, P., McEliece, R.J. and Taylor, H., Ramsey bounds for graph products. Pacific J. Math. v37. 45-46.

Google Scholar

[3]

Ryser, H.J., Combinatorial mathematics. 1963. The Mathematical Association of America.

Google Scholar

Cited By

View all

Sasao TButler JImai M(2004)A fast method to derive minimum SOPs for decomposable functionsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015250(585-590)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015250
Sasao TButler JGoto S(2001)On the minimization of SOPs for bi-decomposition functionsProceedings of the 2001 Asia and South Pacific Design Automation Conference10.1145/370155.370327(219-224)Online publication date: 30-Jan-2001
https://dl.acm.org/doi/10.1145/370155.370327

Recommendations

An improved attribute reduction scheme with covering based rough sets

A simpler approach to attribute reduction based on discernibility matrix is presented with covering based rough sets.Some important properties of attribute reduction with covering based rough sets are improved.The computational complexity of the ...
New ZCZ sequence sets composed of two subsets
TELE-INFO'07: Proceedings of the 6th WSEAS Int. Conference on Telecommunications and Informatics

The present paper proposes new ZCZ sequence sets which consist of two subsets. The most important property of the proposed ZCZ sequence sets is that the cross-correlation function between two arbitrary sequences which belong to different subsets has ...
Large Product-Free Subsets of Finite Groups

A subset of a group is said to beproduct-freeif the product of two of its elements is never itself an element of the subset. Using the classification of finite simple groups, we prove that every finite group of ordernhas a product-free subset of more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Discrete Mathematics Volume 5, Issue 4

August, 1973

104 pages

ISSN:0012-365X

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 August 1973

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sasao TButler JImai M(2004)A fast method to derive minimum SOPs for decomposable functionsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015250(585-590)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015250
Sasao TButler JGoto S(2001)On the minimization of SOPs for bi-decomposition functionsProceedings of the 2001 Asia and South Pacific Design Automation Conference10.1145/370155.370327(219-224)Online publication date: 30-Jan-2001
https://dl.acm.org/doi/10.1145/370155.370327

Abstract

References

Cited By

Recommendations

An improved attribute reduction scheme with covering based rough sets

New ZCZ sequence sets composed of two subsets

Large Product-Free Subsets of Finite Groups

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations