Logo LIP Logo ENS Lyon Logo UCBL

JCRAA 2012: Quelques aspects de l'entropie en combinatoire

Résumé

Ces journées ont pour but de présenter quelques applications de la notion d'entropie à des problèmes combinatoire. Deux directions bien distinctes seront discutées selon que l'on cherchera à optimiser la fonction entropie de Shannon, ou que l'on considèrera la complexité de Kolmogorov. Les principales applications que nous verrons concernent le nombre maximum de couplages dans un graphe biparti ayant un nombre fixé d'arêtes, les colorations non répétitives de graphes, le nombre minimum de portes dans un circuit, le tirage aléatoire d'arbres couvrants et de couplages, le Lemme local de Lovász, les tris...

Programme

Jeudi 28 Juin 2012

Vendredi 29 Juin 2012

Liste des participants

Informations utiles

Valid XHTML 1.1