Category: seminars
Parking sur l’arbre binaire infini
Considérons un arbre enraciné dont les sommets seront interprétés comme des places de parking, chaque place pouvant accueillir au maximum une voiture. Sur chaque sommet de l’arbre, on ajoute une étiquette entière et positive représentant le nombre de voitures arrivant sur ce sommet. Chaque voiture essaie de se garer ...
Étude énumérative des intervalles dans les treillis de type Tamari
summary: Le treillis de Tamari est un ordre partiel sur les objets Catalan. De nombreuses descriptions de ce treillis donnent lieu à de nombreuses familles de généralisations, notamment les treillis m-Tamari, nu-Tamari et m-Cambriens. Après une "visite guidée" dans ce zoo des généralisations du treillis de Tamari, je présenterai mon ...
Grands systèmes méandriques et nouille infinie
Poincaré (1912) définit les méandres comme configurations topologiques obtenues à partir de deux courbes fermées simples sur la sphère ayant un nombre fixé de points d'intersection. Ces objets ont été très étudiés depuis, mais la question principale - leur énumération asymptotique - reste ouverte. Je considérerai ici des systèmes méandriques, qui ...
Balanced spanning trees in random geometric graphs
In a recent breakthrough, Montgomery showed that the Erdos-Rényi random graph G(n,p) typically contains all n-vertex trees of maximum degree Delta slightly above the (sharp) connectivity threshold. We consider the random geometric graph G_d(n,r) obtained by independently assigning a uniformly random position in [0,1]^d ...
Edge k-q-colorability of graphs
summary: Given positive integers k, q, we say that a graph is edge k-q-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most q and that the size of a largest color class is at most k ...
The freezing threshold for uniformly random colourings of sparse graphs
summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε ...
Polytopes : théorèmes importants et généralisations conjecturales sur des espaces tropicaux
Certains théorèmes importants concernant les polytopes, par exemple le g-théorème et le problème de Minkowski, se trouvent à l'interaction de domaines des mathématiques dont on ne soupçonnerait pas la diversité au premier abord. Divers résultats plus ou moins récents en géométrie algébrique, en géométrie tropicale ou en théorie de ...
Musical juggling: from combinatorial modeling to computer assistance with artistic creation (a thesis in the making)
summary: Musical juggling consists of producing music by the very act of juggling. In this context (stemming from a
collaboration between computer science researchers at LISN and a juggling artist), we refer more specifically to
juggling with balls that each produce a musical note when caught.
The aim of this ...
The χ-binding function of d-directional segment graphs
summary: To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore, the chromatic number χ is lower-bounded by the clique number ω. In general, there are no upper bounds on χ in terms of ω. The graphs for which we ...
Complexité en états : Renverser un langage réduit la complexité de l'opération racine.
summary: Les automates (DFA) sont des machines à états qui acceptent ou rejettent des mots. L'ensemble des mots reconnus par un automate est son langage. Les langages rationnels coïncident avec les langages reconnaissable par des automates. Ici nous allons nous intéresser à une mesure, à savoir la complexité en ...