An improved lower bound on the Shannon capacities of complements of odd cycles

Abstract

Improving a 2003 result of Bohman and Holzman, we show that for $n\ge 1$, the Shannon capacity of the complement of the $2n+1$-cycle is at least $(2^{r_n}+1{)}^{1/r_n}=2+\Omega (2^{-r_n}/r_n)$, where $r_n=\exp (O((\log n{)}^2))$ is the number of partitions of $2(n-1)$ into powers of $2$. We also discuss a connection between this result and work by Day and Johnson in the context of graph Ramsey numbers.

arXiv comment7 pages, 1 figure; final version

Cited by in corpus (1)

• Short monochromatic odd cycles