Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 05 mars 2020 à 14h00 en B107, Rado Rakotonarivo nous parlera de : On the combinatorics of lattice polytopes, random sampling and enumeration (soutenance de thèse)

Résumé : This thesis gathers several works on the lattice polytopes of IR^d. In particular, it focuses on the combinatorics of the family of the d-dimensional lattice polytopes contained in the [0,k]^d hypercube, denoted (d,k)-polytopes. Due to their elusive combinatorics, a direct approach using the symbolic method is out of reach. Hence, we propose an original approach based on the description of a graph whose vertex set is the set of (d,k)-polytopes. In this graph, there is an edge between two polytopes if we can transform each of them into the other by an elementary move. These elementary moves are local operations performed on the polytopes. Proceeding this way, we prove that the graph we defined is connected and we obtain a uniform random sampler based on a Markov Chain for the (d,k)-polytopes of arbitrary dimension. We obtain also obtain two exhaustive enumeration algorithms. The first part of this thesis focuses on the description of the above mentionned elementary moves and the study of the graphs based upon them. The second part presents the random sampling and the exhaustive enumeration algorithms. Jury members: Anna Ben-Hamou, Olivier Bodini, Éric Colin de Verdière, Jean-François Marckert, Vincent Pilaud, Mario Valencia-Pabon.


Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr