Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T16:19:51.740Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Normalized Shannon Capacity of a Union

Part of: Communication, information Graph theory

Published online by Cambridge University Press:  03 March 2016

PETER KEEVASH  and
EOIN LONG
PETER KEEVASH
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Woodstock Rd, Oxford OX2 6GG, UK (e-mail: keevash@maths.ox.ac.uk)
EOIN LONG
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: eoinlong@post.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let G1 × G2 denote the strong product of graphs G1 and G2, that is, the graph on V(G1) × V(G2) in which (u1, u2) and (v1, v2) are adjacent if for each i = 1, 2 we have ui = vi or uivi ∈ E(Gi). The Shannon capacity of G is c(G) = limn → ∞ α(Gn)1/n, where Gn denotes the n-fold strong power of G, and α(H) denotes the independence number of a graph H. The normalized Shannon capacity of G is

$$C(G) = \ffrac {\log c(G)}{\log |V(G)|}.$$
Alon [1] asked whether for every ε < 0 there are graphs G and G′ satisfying C(G), C(G′) < ε but with C(G + G′) > 1 − ε. We show that the answer is no.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 94A05: Communication theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 5 , September 2016 , pp. 766 - 767
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Alon, N. (1998) The Shannon capacity of a union. Combinatorica 18 301–310.Google Scholar
[2] Alon, N. (2002) Graph powers, Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, pp. 11–28.Google Scholar
[3] Alon, N. and Lubetzky, E. (2006) The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans. Inform. Theory 52 2172–2176.CrossRefGoogle Scholar
[4] Alon, N. and Orlitsky, A. (1995) Repeated communication and Ramsey graphs. IEEE Trans. Inform. Theory 41 1276–1289.CrossRefGoogle Scholar
[5] Haemers, W. (1979) On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 231–232.CrossRefGoogle Scholar
[6] Körner, J. and Orlitsky, A. (1998) Zero-error information theory. IEEE Trans. Inform. Theory 44 2207–2229.CrossRefGoogle Scholar
[7] Lovász, L. (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 1–7.CrossRefGoogle Scholar
[8] Shannon, C. E. (1956) The zero-error capacity of a noisy channel IRE Trans. Inform. Theory 2 8–19.CrossRefGoogle Scholar