A limit theorem for the shannon capacities of odd cycles
by
Tom Bohman
Carnegie Mellon University

The shannon capacity of a graph gives a measure of the optimal zero-error performance of an associated noisy communication channel. The shannon capacities of the odd cycles having seven or more vertices are not known. In this talk, we discuss a construction for independent sets in the powers of odd cycles. It follows from this construction that the shannon capacity is nearly equal to the fractional vertex packing number (and the Lovasz theta function) for large odd cycles.

Date received: April 22, 2001