Laboratoire d'informatique de l'École polytechnique

Exposé par Nathan Williams: «Independence posets»

Speaker: Nathan Williams
Location: Salle Philippe Flajolet, LIX
Date: Mer. 12 juin. 2019, 11h00-12h00

Pour la dernière séance de l’année, le séminaire Combi du Plateau de Saclay accueille Nathan Williams de l’université de Dallas. Il nous parlera de “Independence Posets”. Le résumé est disponible ci-dessous. Le séminaire aura lieu à 11h en salle Philippe Flajolet au LIX. Par ailleurs, à 15h, Alina Mayorova soutient sa thèse dans l’amphithéâtre Sophie Germain.

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

Résumé: Let G be an acylic directed graph. For each vertex of G, we define an involution on the independent sets of G. We call these involutions flips, and use them to define a new partial order on independent sets of G.

Trim lattices generalize distributive lattices by removing the graded hypothesis: a graded trim lattice is a distributive lattice, and every distributive lattice is trim. Our independence posets are a further generalization of distributive lattices, eliminating also the lattice requirement: an independence poset that is a lattice is always a trim lattice, and every trim lattice is the independence poset for a unique (up to isomorphism) acyclic directed graph G. This is joint work with Hugh Thomas.