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 <
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 (
Informations complémentaires : http://www.math.univ-paris13.fr/~tournier/dimeres2016/
Une journée est organisée sur le thème de la croissance-fragmentation jeudi 17 novembre salle B407 (Bâtiment B, 4ème étage), Université Paris 13, voir ici pour un plan https://www.math.univ-paris13.fr/laga/index.php/fr/laboratoire/venir Le programme est le suivant :
10h-11h, Quan SHI (P13) : Introduction to growth-fragmentation processes
Self-similar growth-fragmentation processes have been introduced in Bertoin [hal-01152370] to describe particle systems in which each particle grows and splits randomly and independently of the others. In this talk, we will first review the constructions and fundamental properties of growth-fragmentations, and then introduce the martingales studied in Bertoin et al. [arXiv:1605.00581].
11h30-12H30, Igor KORTCHEMSKI (X) : Processus de croissance-fragmentation auto-similaires et cartes planaires aléatoires
Les processus de croissance-fragmentation sont des processus stochastiques, récemment introduits par Bertoin, qui décrivent l'évolution de la taille (qui peut croître et décroître) de particules pouvant parfois se disloquer de manière conservative. Nous identifierons une famille à un paramètre de processus de croissance-fragmentation auto-similaires étroitement liés à des processus de Lévy stables, qui apparaissent dans des limites d'échelle d'explorations markoviennes de certaines cartes planaires aléatoires à grand degrés. Il s'agit d'un travail en commun avec Jean Bertoin, Timothy Budd et Nicolas Curien.
14h-15h : Benjamin DADOUN (Zurich) : Comportements asymptotiques des croissance-fragmentations autosimilaires
Le comportement asymptotique de mesures empiriques associées aux fragmentations autosimilaires "pures" (sans croissance) a été étudié sous différents aspects par Bertoin et al. au début des années 2000. Nous traitons cette question lorsque de la croissance est ajoutée aux fragments. Comme pour les fragmentations pures, les martingales additives et leur uniforme intégrabilité jouent un rôle essentiel. Dans le cas homogène, le lien étroit avec les marches aléatoires branchantes permet notamment d'établir une loi forte pour certaines mesures empiriques et de préciser le comportement du plus gros fragment. Nous discuterons ensuite du cas autosimilaire, en exploitant les propriétés des martingales malthusiennes démontrées récemment par Bertoin, Budd, Curien et Kortchemski (2016+).
15h30-16h30 : Marie DOUMIC (INRIA Rocquencourt), TBA
Contact : Bénédicte Haas
Les exposés auront lieu dans la salle B407 (Bâtiment B, 4ème étage), voir ici pour un plan https://www.math.univ-paris13.fr/laga/index.php/fr/laboratoire/venir
Journée "Arbres en algèbre, combinatoire et probabilités"
16 Juin 2016
Université Paris 13, salle B405, LAGA
Programme:
10h-11h : "Approche homotopique des probabilités libre d'après Drummond-Cole-Park-Terilla" [Bruno Vallette, Université Paris 13]
11h30-12h30 : "Des séries en arbres aux séries de type Dirichlet" [Frédéric Chapoton, Université de Strasbourg]
Déjeuner
14h-15h : "Sur une généralisation des probabilités libres en matrices aléatoires" [Camille Male, Université Paris Descartes]
15h30-16h30 : "Cumulants libres non-commutatifs" [Jean-Yves Thibon, Université Paris-Est Marne-la-Vallée]
Résumés :
"Approche homotopique des probabilités non-commutatives d'après Drummond-Cole-Park-Terilla" [Bruno Vallette, Université Paris 13]
Le but de cet exposé est d'offrir un résume aussi élémentaire que possible de l'approche homotopique proposée par Drummond-Cole?Park?Terilla des cumulants apparaissant en probabilité non-commutative. Le point principal consiste à interpréter ces derniers comme des infini-morphismes des algèbres à homotopie près sur certaines opérades de Koszul. On retrouve alors toutes les formules de cumulants des probabilités non-commutative à l'aide des formules d'inversion des infini-isomorphismes et de l'action du groupe de jauge de la théorie de la déformation des algèbres à homotopie près. Aucun prérequis n'est nécessaire pour suivre cet exposé; toutes les notions seront rappelées, ce qui permettra aussi de servir d'introduction aux autres exposés de la journée.
"Des séries en arbres aux séries de type Dirichlet" [Frédéric Chapoton, Université de Strasbourg]
Je présenterai deux séries en arbres particulières qui jouent un rôle comparable à celui de l'exponentielle et du logarithme, et qui apparaissent naturellement en analyse numérique. J'expliquerai ensuite comment une déformation du "logarithme en arbres" est motivée par certaines considérations algébriques. Je donnerai une description des coefficients de ce q-logarithme en arbres
en termes de certains polytopes, et éventuellement la relation entre certains de ces coefficients et des séries de type Dirichlet.
"Sur une généralisation des probabilités libres en matrices aléatoires" : [Camille Male, Université Paris Descartes]
Certains modèles de matrices aléatoires hermitiennes ont la propriété de se diagonaliser dans une base qui n'est pas "asymptotiquement uniformément distribuée" lorsque la taille des matrices tend vers l'infini, contrairement aux matrices classiques de Wigner ou de Wishart. En conséquence, les distributions asymptotiques de valeurs propres de polynômes hermitiens en de telles matrices indépendantes diffèrent parfois des prédictions données par les probabilités libres.
Un espace de probabilités non commutatif étant une algèbre munie d'une forme linéaire, nous verrons qu'il est possible grace aux opérades d'introduire une notion de variable non commutative plus riche qui permet de calculer les moments de ces distributions dans des cas variés. Les résultats sont exprimés en termes d'une notion d'indépendance qui unifie l'indépendances classique (tensorielle), l'indépendance libre de Voiculescu et encode également d'autres relations.
"Cumulants libres non-commutatifs" [Jean-Yves Thibon, Université Paris-Est Marne-la-Vallée]
L'équation fonctionnelle définissant les cumulants libres dans le cas d'une seule variable aléatoire peut être relevée successivement à l'algèbre de Faà di Bruno non-commutative, puis au groupe d'une opérade libre. La solution de cette équation prend en compte le cas d'une mesure à valeurs opératorielles, et redonne la formule de Speicher dans le cas d'une mesure scalaire. On peut aussi interpréter cette équation comme une généralisation de celle d'Ebrahimi-Fard et Patras.
Tous les détails de cette rencontre sont disponibles à l?adresse suivante : https://www.math.univ-paris13.fr/~hoffbeck/CombOperadProba/ <https://www.math.univ-paris13.fr/~hoffbeck/CombOperadProba/>
Deux pauses cafés et le déjeuner sont prévus. Si vous pensez venir, merci de nous prévenir par courriel à
N'oubliez pas de venir avec une copie de ce message ou de la page de la rencontre pour pouvoir entrer dans le campus.
11h-12h : Vincent Tassion (Genève) : A new proof of the sharpness of the phase transition for Bernoulli percolation on Z^d (based on a joint work with Hugo Duminil-Copin)