The shannon capacity on C(n,k)

This thesis focuses on a problem formulated by Claude Shannon named the Shannon capacity. This problem is about information rate per time unit over a noisy channel. The noisy channel is here represented by a graph. We specifically focus on a class of circulant graphs that are denoted by C(n,k) with vertex set z/nz, where all vertices are...

The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs

This thesis is about maximum independent set and chromatic number problems on certain kinds of infinite graphs. A typical example comes from the Witsenhausen problem: For $n \geq 2$, let $S^{n-1} := \{ x \in \R^n : \|x\|_2 =1 \}$ be the unit sphere in $\R^n$, and let $G=(V,E)$ be the graph with $V = S^{n-1}$, in which two points in $S^{n-1}$ are...

The Shannon capacity of graphs

In this thesis you will find an overview of the main results of Lovasz and Shannon, together with a substantial set of examples for which we have computed the Shannon capacity. Also, some graphs for which it is not possible to calculate the Shannon capacity are given.