Séminaire de Janos Korner (Univ. Roma La Sapienza) Partager ce post

Entropies and capacity of graphs

  • Le 09/04/2015 à 10h30
  • En C48, site Barrault

Entropies and capacity of graphs


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.

Partager ce post