Laboratoire d'informatique de l'École polytechnique

Exposé par Marie Théret: «Cardinal d'un ensemble de coupure minimal en percolation de premier passage»

Speaker: Marie Théret
Location: Salle Philippe Flajolet (LIX)
Date: Mer. 27 nov. 2019, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Marie Théret (Université Paris Nanterre) nous parlera de Cardinal d'un ensemble de coupure minimal en percolation de premier passage

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé : On considère le modèle de percolation de premier passage sur Z^d en dimension d≥2 : on associe aux arêtes du graphe une famille de variables i.i.d. positives ou nulles. On interprète la variable aléatoire associée à une arête comme étant sa capacité, i.e., la quantité maximale d'eau ou d'information qui peut la traverser par seconde. Il en découle une définition naturelle de flux maximal à travers une région bornée du graphe entre un ensemble d'émetteurs et un ensemble de récepteurs. Ce flux maximal est égale à la capacité minimale d'un ensemble de coupure, c'est-à-dire un ensemble d'arêtes tel que si on le retire du graphe on disconnecte totalement les émetteurs des récepteurs. Dans cet exposé, on s'intéressera à une des caractéristiques de cet ensemble de coupure minimal : son cardinal. Il s'agit d'un travail en collaboration avec Barbara Dembin (LPSM, Université de Paris)