On the combinatorics of lattice polytopes, random sampling and enumeration

Sur la combinatoire des polytopes en nombres entiers, génération aléatoire et enumération

Rado Rakotonarivo (1)

1 LIPN - Laboratoire d'Informatique de Paris-Nord

This thesis gathers several works on the lattice polytopes of Rd. 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.

Cette thèse regroupe des travaux sur les polytopes en nombres entiers de Rd. Elle s’intéresse en particulier à la combinatoire des polytopes de dimension d contenus dans un hypercube [0,k]d, notés (d,k)polytopes.Comptetenudeladifficultéd’uneapprochedirecteparlaméthodesymbolique,nousproposons une approche originale au moyen de la description d’une structure de graphe dont les sommets sont les (d,k)-polytopes. Les arêtes du graphe sont définies par des opérations élémentaires agissant comme des transformations locales sur les polytopes. Nous prouvons que ce graphe est connexe et permet d’obtenir un générateur aléatoire uniforme via une chaîne de Markov en dimension générale. Nous aboutissons également à deux algorithmes de génération exhaustive. Une première partie de nos travaux se concentre sur la description de ces opérations élémentaires ainsi que sur l’étude des structures de graphes se basant sur ces dernières. Une deuxième partie présente les algorithmes de génération aléatoire et de génération exhaustive.

Mots clés: Convex polygons; Polytopes; Lattice polytopes

Mots clés: Polygones convexes; Polytopes; Polytopes en nombres entiers; Chaîne de Markov; Géométrie discrète

Domaines: Informatique et langage [cs.CL]

Rado Rakotonarivo. Sur la combinatoire des polytopes en nombres entiers, génération aléatoire et enumération. Informatique et langage [cs.CL]. Université Paris-Nord - Paris XIII, 2020. Français. ⟨NNT : 2020PA131013⟩. ⟨tel-03347550⟩