Journée Cartes (9 avril 2019)

Journée Combinatoire (3 juillet 2018)

Journée Combinatoire

3 Juillet 2018

Salle B107, Institut Galilée

Justine Falque                  Algèbre des orbites des groupes à profil polynomial, preuve des conjectures de Cameron et de Macpherson

Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n,  pour l'action induite de G sur les sous-ensembles d'éléments.
Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale.
Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites
de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini.
L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun avec Nicolas  Thiéry (avec les conseils précieux de Peter Cameron lui-même).

Pablo Rotondo                 Efficient GCD computation: the continued logarithm algorithm and ergodic theory

Introduced by Gosper in 1978, the Continued Logarithm Algorithm computes the gcd of two integers efficiently, performing only shifts and subtractions. Shallit has studied its worst-case complexity in 2016, showing it to be linear. Here, we perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values, with explicit constants. Our analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Even though studied by Chan in 2005, this system from an Ergodic Theory perspective, the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadic component and deal with a two-component dynamical system. With this new mixed system at hand, we provide a complete average-case analysis of the algorithm.

Paulina Cecchi                 Dendric words and dendric subshifts

To every factor w of an infinite word x in a finite alphabet, we can associate a bipartite graph, called the extension graph of w, in which one puts edges between left and right copies of letters a, b such
that awb is a factor of x. The word x is said to be dendric if for all factor w of x, the extension graph of w is a tree. Dendric words are
therefore defined in terms of combinatorial properties of their language. Dendric subshifts are symbolic systems defined using dendric words. We will talk about some dynamical properties of dendric subshifts.

Delphin Sénizergues        Degrés limites dans les arbres à attachement préférentiel affine

On introduit le modèle d'arbres suivant. On se donne une suite arbitraire de nombres réels positifs $(a_n)_{n\geq 1}$. On définit $T_1$ comme l'arbre à un seul sommet d'étiquette $1$. Si $T_n$ est déjà construit, $T_{n+1}$ est obtenu en rajoutant un sommet étiqueté $n+1$ à l'arbre $T_n$. Le nouveau sommet est un enfant du sommet $k\geq n$ avec une probabilité proportionnelle à $a_k+deg(k)$, où $deg(k)$ est le degré du sommet dans l'arbre $T_n$. On s'intéressera à l'évolution de la suite des degrés des sommets de l'arbre. Sous certaines conditions sur la suite des réels $(a_n)_{n\geq 1}$, la suite des degrés adéquatement renormalisés converge p.s. (dans $l^p$ pour p assez grand) vers une suite aléatoire, qui peut être décrite comme les accroissements successifs d'une chaîne de Markov. Pour certaines suites $(a_n)$, la loi de la chaîne de Markov est même explicite. La preuve utilise des résultats classiques sur les urnes de Pólya, que je rappellerai.

Journée de Géométrie et Combinatoire dans les Espaces des Modules (24-25 septembre 2018)

Journées de Géométrie et Combinatoire dans les Espaces des Modules

24 et 25 Septembre 2018, Université Paris 13, campus de Villetaneuse

99 avenue Jean-Baptiste Clément, 93430 Villetaneuse (FRANCE)

Orateurs:

Corentin Boissy (Toulouse)
Vincent Delecroix (Bordeaux)
Quentin De Mourgues (LIPN, Villetaneuse)
Giovanni Forni (Maryland)
Vaibhav Gadre (Glasgow)
Elise Goujard (Bordeaux)
Rodolfo Gutierrez (LAGA, Villetaneuse)
Carlos Matheus∗ (LAGA, Villetaneuse)

∗ = à confirmer.

À venir: programme, titres et abstracts des exposées.

Organisateurs: Luca Marchese, Carlos Matheus Santos, Thierry Monteil, Andrea Sportiello.

Inscriptions: Pour s'inscrire, écrire à This email address is being protected from spambots. You need JavaScript enabled to view it.

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.>