Jeudi 29 novembre 2007, à 14h30.
Orateur : János Körner (Univ. Rome "La Sapienza").
Titre : Shearer's inequality and graph entropy.

Inequalities involving Shannon--type (entropy-based) information quantities have been playing a crucial role in information theory and came to the forefront even more with the recent interest in network information theory. On the other hand, a very few simple inequalities involving entropies have been used repeatedly and with great success in combinatorics. In particular, a clever extension of the sub-additivity of Shannon's entropy was noticed by Shearer. In an other direction, the sub-additivity of graph entropy with respect to the union of graphs and especially the cases of equality therein reflect important structural properties of graphs.

The talk is in two parts. The first part is a brief survey on graph entropy and its applications in structural graph theory and computer science. In the second part, based on recent joint work with Emanuela Fachini, we show that Shearer's inequality has a simple and straightforward generalization to graph entropy.