On the Shannon Capacity of Triangular Graphs
| Authors | |
|---|---|
| Year of publication | 2013 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Journal of Combinatorics |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p27 |
| Field | Information theory |
| Keywords | cube packing; Shannon capacity; tabu search; zero-error capacity |
| Description | The Shannon capacity of a graph $G$ is defined as $c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$ where $\alpha(G)$ is the independence number of $G$. The Shannon capacity of the Kneser graph $\kg{n}{r}$ was determined by Lov\'{a}sz in 1979, but little is known about the Shannon capacity of the complement of that graph when $r$ does not divide $n$. The complement of the Kneser graph, $\kgc{n}{2}$, has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(\kgc{n}{2}) \geq c(C_n)$, and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discrete $d$-dimensional torus of width $n$ using two types of $d$-dimensional cubes of width $2$. Bounds on $c(\kgc{n}{2})$ obtained in this work include $c(\kgc{7}{2}) \geq \sqrt[3]{35} \approx 3.271$, $c(\kgc{13}{2}) \geq \sqrt[3]{248} \approx 6.283$, $c(\kgc{15}{2}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(\kgc{21}{2}) \geq \sqrt[4]{11441} \approx 10.342$. |
| Related projects: |