On the normalized Shannon capacity of a union
classification
🧮 math.CO
keywords
capacityepsilonshannonalphadenotesgraphgraphsnormalized
read the original abstract
Let $G_1 \times G_2$ denote the strong product of graphs $G_1$ and $G_2$, i.e. the graph on $V(G_1) \times V(G_2)$ in which $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent if for each $i=1,2$ we have $u_i=v_i$ or $u_iv_i \in E(G_i)$. The Shannon capacity of $G$ is $c(G) = \lim_{n\to \infty} \alpha (G^n)^{1/n}$, where $G^n$ denotes the $n$-fold strong power of $G$, and $\alpha (H)$ denotes the independence number of a graph $H$. The normalized Shannon capacity of $G$ is $C(G) = \frac {\log c(G)}{\log |V(G)|}$. Alon asked whether for every $\epsilon > 0$ there are graphs $G$ and $G'$ satisfying $C(G), C(G') < \epsilon$ but with $C(G + G') > 1 - \epsilon $. We show that the answer is no.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.