Jeudi 9 avril 2015 à 10h30 en salle C48
János Körner (Università di Roma)

Titre : Entropies and capacity of graphs

Résumé :
In the early seventies the speaker introduced two complementary notions of graph entropy. One of these leads to information­ theoretic characterisations and generalisations of perfect graphs and to asymptotically optimal sorting algorithms for partially ordered sets. Here we deal with the complementary notion to show how it might lead to a new upper bound for the Shannon capacity of self-complementary vertex-transitive graphs matching the Lovász bound based on his theta function.