On the Shannon Capacity of Triangular Graphs

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ASHIK Mathew Kizhakkepallathu PATRIC R. J. Östergard POPA Alexandru

Year of publication 2013
Type Article in Periodical
Magazine / Source Electronic Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.