On the Shannon Capacity of Graphs

This talk is focused on the Shannon capacity of graphs. We introduce either exact results or new bounds of the Shannon capacity for two families of graphs: the q-Kneser and Tadpole graphs. An inequality relating the strong product of graphs to their disjoint union is derived, which has the potential to reduce computational complexity and to yield simpler and shorter proofs for known bounds on disjoint unions. Following Schrijver’s recent approach, we study conditions under which the Shannon capacity of any polynomial of graphs equals the corresponding polynomial of their individual Shannon capacities, thereby significantly simplifying the computation of the Shannon capacity in these cases. We also examine conditions under which the Shannon capacity of a graph is not attained by any finite power of its independence number, providing an alternative approach in comparison to an earlier work by Watanabe, and providing additional insights.

M.Sc. student under the supervision of Prof. Igal Sason.