Capacidad de Shannon de un grafo y el número de Lovász

Abstract

La capacidad de Shannon de un grafo describe la máxima cantidad de información que se puede transmitir de manera fiable utilizando un grafo como modelo de las restricciones impuestas por un canal de comunicación con ruido. El número de Lovász o función theta de Lovász es un parámetro del grafo que proporciona una cota superior para la capacidad de Shannon y puede calcularse de manera más sencilla y eficiente. Mediante esta función, Lovász consiguió demostrar por ejemplo que la capacidad de Shannon de un grafo C5 es √ 5. Este trabajo profundiza en ambos conceptos tomando como base el artículo original de Lovász de 1979. Además, también se incluyen algunos teoremas muy recientes sobre la capacidad de Shannon de grafos fuertemente regulares.

The Shannon capacity of a graph describes the maximum amount of information that can be reliably transmitted using a graph as a model of the restrictions imposed by a noisy communication channel. The Lovász number or Lovász theta function is a graph parameter that provides an upper bound for the Shannon capacity and can be calculated more easily and efficiently. Using this function, Lovász was able to demonstrate, for example, that the Shannon capacity of a C5 graph is in fact √ 5. This work explores both concepts taking as its starting point Lovász’s original 1979 paper. Additionally, some very recent theorems on the Shannon capacity of strongly regular graphs are also included.