Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-30T00:53:30.333Z Has data issue: false hasContentIssue false
  • English
  • Français

On Extremal Set Partitions in Cartesian Product Spaces

Published online by Cambridge University Press:  12 September 2008

Rudolf Ahlswede  and
Ning Cai
Rudolf Ahlswede
Affiliation:
Universität Bielefeld, Fakultät für Mathematik, Postfach 100131, 33501 Bielefeld, Germany
Ning Cai
Affiliation:
Universität Bielefeld, Fakultät für Mathematik, Postfach 100131, 33501 Bielefeld, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

The partition number of a product hypergraph is introduced as the minimal size of a partition of its vertex set into sets that are edges. This number is shown to be multiplicative if all factors are graphs with all loops included.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 3 , September 1993 , pp. 211 - 220
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ahlswede, R. (preprint) On set coverings in Cartesian product spaces, Manuscript 1971. Reprinted in SFB 343 Diskrete Strukturen in der Mathematik, Preprint 92–034.Google Scholar
[2]Ahlswede, R. (1979) Coloring hypergraphs: A new approach to multi-user source coding, Pt I. Journ. of Combinatorics, Information and System Sciences 4 (1) 76–115.Google Scholar
[3]Ahlswede, R. (1980) Coloring hypergraphs: A new approach to multi-user source coding, Pt II. Journ. of Combinatorics, Information and System Sciences 5 (3) 220–268.Google Scholar
[4]Ahlswede, R. and Cai, N. (preprint) On POS partition and hypergraph products. SFB 343 Diskrete Strukturen in der Mathematik, Preprint 93–008.Google Scholar
[5]Ahlswede, R., Cai, N. and Zhang, Z. (1989) A general 4-words inequality with consequences for 2-way communication complexity. Advances in Applied Mathematics 10 75–94.CrossRefGoogle Scholar
[6]Gallai, T. (1963) Neuer Beweis eines Tutte'schen Satzes. Magyar Tud. Akad. Mat. Kutato Int. Közl. 8 135–139.Google Scholar
[7]Lovasz, L. (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory IT-25 1–7.CrossRefGoogle Scholar
[8]Lovász, L. and Plummer, M. D. (1986) Matching Theory, North-Holland Mathematics studies 121, North-Holland.Google Scholar
[9]Mehlhorn, K. and Schmidt, E. M. (1982) Las Vegas is better than determinism in VLSI and distributed computing. Proceedings 14th ACM STOC 330–337.Google Scholar
[10]Posner, E. C. and Mc Eliece, R. J. (1971) Hide and seek, data storage and entropy. Annals of Math. Statistics 42 1706–1716.Google Scholar
[11]Shannon, C. E. (1956) The zero-error capacity of a noisy channel. IEEE Trans. Inform. Theory IT-2 8–19.CrossRefGoogle Scholar
[12]Yao, A. (1979) Some complexity questions related to distributive computing. Proceedings 11th ACM STOC 209–213.Google Scholar