On the Normalized Shannon Capacity of a Union

Peter Keevash; Eoin Long

doi:10.1017/S0963548316000055

On the Normalized Shannon Capacity of a Union

Peter Keevash, Eoin Long

Mathematics

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

7 Citations (Scopus)

Abstract

Let G₁ × G₂ denote the strong product of graphs G₁ and G₂, that is, the graph on V(G₁) × V(G₂) in which (u₁, u₂) and (v₁, v₂) are adjacent if for each i = 1, 2 we have u_i= v_i or u_iv_i ∈ E(G_i). The Shannon capacity of G is c(G) = lim_{n → ∞} α(Gⁿ)^1/n , where Gⁿ 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) = 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.

Original language	English
Pages (from-to)	766-767
Number of pages	2
Journal	Combinatorics, Probability and Computing
Volume	25
Issue number	5
Early online date	3 Mar 2016
DOIs	https://doi.org/10.1017/S0963548316000055
Publication status	Published - 1 Sept 2016

Keywords

Shannon capacity

Access to Document

10.1017/S0963548316000055Licence: None: All rights reserved

Cite this

@article{34a0f5daad004bf6852dabd90cac2dd0,

title = "On the Normalized Shannon Capacity of a Union",

abstract = "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 isC(G) = 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.",

keywords = "Shannon capacity",

author = "Peter Keevash and Eoin Long",

year = "2016",

month = sep,

day = "1",

doi = "10.1017/S0963548316000055",

language = "English",

volume = "25",

pages = "766--767",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

T1 - On the Normalized Shannon Capacity of a Union

AU - Keevash, Peter

AU - Long, Eoin

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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 isC(G) = 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.

AB - 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 isC(G) = 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.

KW - Shannon capacity

U2 - 10.1017/S0963548316000055

DO - 10.1017/S0963548316000055

M3 - Article

SN - 0963-5483

VL - 25

SP - 766

EP - 767

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 5

ER -

On the Normalized Shannon Capacity of a Union

Abstract

Keywords

Access to Document

Fingerprint

Cite this