Journée Combinatoire et probabilités (22 mai 2018)

Combinatoire et probabilités

mardi 22 mai 2018

Cette journée sera consacrée aux questions liant combinatoire et probabilités. Elle s'inscrit dans le cadre de l'axe 3 (Physique Statistique, Combinatoire) du pôle Math-STIC de l'Université Paris 13, qui fédère les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI).

La conférence a lieu en salle B107 du LIPN, voir infos pratiques ci-dessous.

Programme

10h30 : Michael Wallner (université de Bordeaux) : Periodic Pólya urns and an application to Young tableaux

Résumé : Pólya urns are urns where at each unit of time a ball is drawn uniformly at random and is replaced by some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p. Our key tool are generating functions, which encode all possible urn compositions after a certain number of steps. The evolution of the urn is then translated into a system of differential equations and we prove that the moment generating functions are D-finite. From these we derive asymptotic forms of the moments. When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. Furthermore, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.


11h30 : Alain Rouault (LMV, UVSQ) : Troncatures de matrices de Haar et draps browniens

Résumé : Ce travail (en collaboration avec C. Donati-Martin et V. Beffara) est une extension d'un article de G. Chapuy (2007), obtenue en remplaçant le groupe des permutations d'ordre n muni de la probabilité uniforme par le groupe unitaire (resp. orthogonal) d'ordre n. On définit ainsi une suite indexée par n de processus à deux paramètres qui converge en loi vers un drap brownien. Les preuves mettent en jeu la combinatoire associée au calcul de Weingarten.

 

12h30: Lunch 

14h : Anna Ben Hamou (LPSM, UPMC) : Temps de mélange de marches aléatoires sur des graphes aléatoires

Résumé : Dans cet exposé, nous commencerons par rappeler la notion de temps de mélange d'une chaîne de Markov et introduirons le phénomène de cutoff, qui décrit une convergence très abrupte à l'équilibre. Établir le cutoff pour une chaîne donnée requiert souvent une analyse extrêmement fine, et il existe assez peu de résultats généraux permettant par exemple d'exhiber des grandes classes de graphes sur lesquels la marche aléatoire présente le cutoff. On peut alors se demander ce qu'il se passe sur un graphe « typique ». Nous considérerons le cas des graphes aléatoires à suite prescrite de degrés, et montrerons qu'avec forte probabilité, sur de tels graphes, la marche aléatoire simple et la marche aléatoire dite « sans rebroussement » présentent le cutoff. En interprétant les temps de mélange comme des entropies limites sur un arbre de Galton-Watson qui constitue une approximation locale du graphe, nous montrerons de plus que la marche aléatoire sans rebroussement mélange plus vite que la marche simple. Ces résultats sont issus de collaborations avec Justin Salez (Paris Diderot), Eyal Lubetzky (NYU) et Yuval Peres (Microsoft Research).



15h : Guillaume Chapuy (IRIF, Paris Diderot) : Énumération de variétés triangulées en dimension d≥3

Résumé : En dimension d≥3, on prend n simplexes, et on recolle leurs facettes de manière arbitraire. On obtient ainsi un espace topologique qui est a priori une pseudo-variété, mais pas toujours une variété. De combien de manière peut-on le faire, asymptotiquement, pour obtenir une variété? On donne des réponses (très) partielles à cette question sous la forme de bornes inférieures et supérieures superexponentielles. En particulier on détermine le comportement surexponentiel en dimension 3, dans le cas des triangulations coloriées issues des modèles de tenseur. Au passage on croise des questions rigolotes et nouvelles d'énumération de graphes que nous laissons partiellement ouvertes. Travail en commun avec Guillem Perarnau.

 

Aspects pratiques

Les exposés se tiendront en salle B107 (Bâtiment B, 1er étage) de l'institut Galilée, Université Paris 13.

Contact : Cyril Banderier <cyril.banderierThis email address is being protected from spambots. You need JavaScript enabled to view it., Philippe Marchal <This email address is being protected from spambots. You need JavaScript enabled to view it.>

Journée "Flips" (28 novembre 2017)

FLIPS

mardi 28 novembre 2017

Cette journée sera consacrée aux problèmes de flips. Elle s'inscrit dans le cadre de l'axe 3 (Physique Statistique, Combinatoire) du pôle Math-STIC de l'Université Paris 13, qui fédère les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI).

La conférence a lieu en salle B107 du LIPN, voir infos pratiques ci-dessous.

Programme

10h: Alexander Pilz (ETH Zürich) : Determining the flip distance between triangulations of simple polygons and point sets

In this talk, we consider edge exchange flips in triangulations of point sets and simple polygons. In particular, it addresses the question whether the length of the shortest sequence of flips for transforming one given triangulation into another can be determined in polynomial time. We present a proof showing that the corresponding optimization problem is APX-hard for triangulations of point sets. For triangulations of simple polygons, we give a reduction showing NP-completeness of the decision version of the problem. The two proofs are fundamentally different, but use a common sub-structure, the well-known double chain, whose properties with respect to flip graphs we investigate. Finally, we point out some difficulties in solving the flip distance problem for triangulations of convex polygons, which is still open. Based in part on joint work with  Oswin Aichholzer and Wolfgang Mulzer.

11h15: Thomas Budzinski (École Normale Supérieure) : On the mixing time of the flip walk on triangulations of the sphere

A simple way to sample a uniform triangulation of the sphere with a fixed number $n$ of vertices is a Monte-Carlo method: we start from an arbitrary triangulation and flip repeatedly a uniformly chosen edge. We prove a lower bound of order n^(5/4) on the mixing time of this Markov chain.

12h30: Lunch

14h: Lionel Pournin (LIPN, Université Paris 13) : Eccentricities in the flip-graphs of convex polygons

The flip-graph of a convex polygon π is the graph whose vertices are the triangulations of π and whose edges correspond to flips between them. The eccentricity of a triangulation T of π is the largest possible distance in this graph from T to any triangulation of π. Let n stand for the number of vertices of π. It is well known that, when all n-3 interior edges of T are incident to a given vertex, the eccentricity of T in the flip-graph of π is exactly n-3. The purpose of this talk is to generalize this statement to arbitrary triangulations of π: if n-3-k denotes the largest number of interior edges of T incident to a vertex, and if k≤n/2-2, the eccentricity of T in the flip-graph of π is exactly n-3+k. Surprisingly, the value of k turns out to characterize eccentricities if it is small enough. More precisely, when k≤n/8-5/2, T has eccentricity n-3+k if and only if exactly n-3-k of its interior edges are incident to a given vertex. A number of related questions will be mentioned and discussed.

15h15: Thomas Fernique (LIPN, Université Paris 13) : Flips in Tilings

Tilings are rigid geometric structures used, for example, to model materials. A flip on tilings is a local operation which changes a tiling into another one, yielding a graph whose nodes are the different tilings and edges connect tilings which differ by a flip. A well-known example are tilings by dominos (1x2 and 2x1 rectangles), where a flip consists in a quarter turn on a 2x2 square tiled by two dominos.
Issues as connectedness of diameter of such graphs (as well as more advanced issues as mixing time of random walks) are of importance to better understand the physical properties of the modeled material. The aim of this talk is to review several examples of flips on tilings and the corresponding results or conjectures.

 

Aspects pratiques

Les exposés se tiendront en salle B107 (Bâtiment B, 1er étage) de l'institut Galilée, Université Paris 13. Cliquer ici pour des plans et moyens d'accès.

Contact : Lionel Pournin <This email address is being protected from spambots. You need JavaScript enabled to view it.

Journée "Marches aléatoires" (6 décembre 2017)

MARCHES ALEATOIRES

mercredi 6 décembre 2017

Cette journée du 6 décembre 2017, consacrée aux aspects combinatoires et probabilistes des marches aléatoires, s'inscrit dans le cadre de l'axe 3 (Physique Statistique, Combinatoire) du pôle Math-STIC de l'Université Paris 13, qui fédère les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI).

La conférence a lieu en salle B407 du LAGA, voir infos pratiques ci-dessous.

 

Programme

 

— 10h : Café —

    • 10h15-11h15. Axel Bacher (LIPN (Paris 13)) :
        TBA
    • 11h30-12h30. Niccolò Torri (LPMA (Paris 6)) :
        La marche prudente.

— Buffet —

    • 14h15-15h15. Kilian Raschel (CNRS, LMPT (Tours)) :
        Extinction de populations faiblement inhomogènes en dimension deux.

— 15h15 : Café —

  • 15h30-16h30. Arvind Singh (CNRS, LMO (Paris 11)) :
      TBA

Aspects pratiques

Les exposés se tiendront en salle B407 (Bâtiment B, 4ème étage) de l'institut Galilée, Université Paris 13. Cliquer ici pour des plans et moyens d'accès.

 

Informations complémentaires : http://www.math.univ-paris13.fr/~tournier/marches2017/

Contact : Laurent Tournier <This email address is being protected from spambots. You need JavaScript enabled to view it.

Journée "Dimères" (13 décembre 2016)

Journée Dimères

13 décembre 2016 - 10h à 16h30

salle B407, LAGA-Institut Galilée

 

Orateurs:

  • Vincent Beffara (CNRS, Grenoble)
  • Cédric Boutillier (Paris 6)
  • Benoît Laslier (Paris 7)
  • Béatrice de Tilière (Paris Est Créteil)

 

Contact : Laurent Tournier (This email address is being protected from spambots. You need JavaScript enabled to view it.)

Informations complémentaires : http://www.math.univ-paris13.fr/~tournier/dimeres2016/