### Abstract

For an undirected graph G = (V, E), let G^{n} denote the graph whose vertex set is V^{n} in which two distinct vertices (u_{1}, u_{2}, . . . , u_{n}) and (v_{1}, v_{2}, . . . , v_{n}) are adjacent iff for all i between 1 and n either u_{i} = v_{i} or u_{i}v_{i} ∈ E. The Shannon capacity c(G) of G is the limit lim_{n→∞} (α(G^{n}))^{1/n}, where α(G^{n}) is the maximum size of an independent set of vertices in G^{n}. We show that there are graphs G and H such that the Shannon capacity of their disjoint union is (much) bigger than the sum of their capacities. This disproves a conjecture of Shannon raised in 1956.

Original language | English (US) |
---|---|

Pages (from-to) | 301-310 |

Number of pages | 10 |

Journal | Combinatorica |

Volume | 18 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1998 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'The Shannon capacity of a union'. Together they form a unique fingerprint.

## Cite this

Alon, N. (1998). The Shannon capacity of a union.

*Combinatorica*,*18*(3), 301-310. https://doi.org/10.1007/PL00009824