- Seminaire.calin - Listes du LIPN

Seminaire CALIN ce mardi : matin et apres-midi
by Thierry Monteil 05 Mar '18

05 Mar '18

Bonjour, ce mardi 06 mars 2018 à 10h30 en B107, Sergey Dovgal nous parlera de : Pólya enumeration theorem from scratch II + discussion Résumé : I am going to talk about very popular combinatorial connection between ordinary and exponential generating functions which is called cycle index function. I am going to define the combinatorial species according to the book "Theory of Species" by Bergeron, Labelle, Leroux, and present their beautiful proof of the cycle index composition theorem. The proof relies on the theory of symmetric functions in infinitely many variables. This proof is a beautiful example of Grothendieck's concept: in order to prove something particular, one should make a more general statement and prove it. L'après-midi, à 14h00 en B107, Sidi Mohamed Sedjelmaci nous parlera de : Two fast parallel GCD algorithms of many integers Résumé : On montre que le calcul du PGCD de 𝑚 integers de 𝑂(𝑛) bits peut se faire en parallèle en temps 𝑂(𝑛 / log 𝑛) avec 𝑂(𝑚𝑛1+𝜖 ) processors, pour tout 2 ≤ 𝑚 ≤ 𝑛3/2 / log 𝑛, c'est-à-dire que le temps de calcul en parallèle ne dépend pas dépend du nombre d'entiers m considéré dans cet intervalle. À demain, Thierry

1 0

Seminaire CALIN ce mardi : matin et apres-midi
by Thierry Monteil 20 Feb '18

20 Feb '18

Bonjour, ce mardi 20 février 2018 à 10h30 en B107, Sergey Dovgal nous parlera de : Pólya enumeration theorem from scratch Résumé : I am going to talk about very popular combinatorial connection between ordinary and exponential generating functions which is called cycle index function. I am going to define the combinatorial species according to the book "Theory of Species" by Bergeron, Labelle, Leroux, and present their beautiful proof of the cycle index composition theorem. The proof relies on the theory of symmetric functions in infinitely many variables. This proof is a beautiful example of Grothendieck's concept: in order to prove something particular, one should make a more general statement and prove it. L'après-midi, à 14h00 en B107, Jérémie Bettinelli nous parlera de : Disques browniens Résumé : À l'instar du mouvement brownien qui apparaît comme limite d'échelle universelle de toute marche aléatoire raisonable, les disques browniens sont des espace métrique aléatoires qui apparaissent comme limite d'échelle universelle de modèles raisonables de cartes aléatoire du disque. Ces objets généralisent la carte brownienne de Miermont et Le Gall obtenue en considérent des cartes aléatoire de la sphère. Nous présenterons les disques browniens et en donneront quelques propriétés remarquables. Ce travail est en commun avec Grégory Miermont. Thierry

1 0

Seminaire CALIN demain : deux exposes
by Thierry Monteil 29 Jan '18

29 Jan '18

Bonjour, demain mardi 30 janvier 2018 à 14h00 en B107, Mohab Safey El Din nous parlera de : The quest of asymptotically fast algorithms for polynomial system solving over the reals Résumé : Polynomial systems arise in many areas of engineering sciences and computer science. Most of the time, the end-user expects some information about the real solution set of the system under study. Algorithmic problems encompass which appear frequently is to decide the existence of real solutions, compute sample points in each connected component of the set under study, compute a description of this set on some affine space or answer connectivity queries. All these problems are NP-hard and, actually the best known complexities to solve them are exponential in the number of variables. Moreover, because of the non-linearity of the considered systems, reliable issues are important. In this talk, I will give an overview of computer algebra algorithms for solving these problems with a focus on those which conciliate practical efficiency with asymptotically optimal complexity. Puis, à 15h00 en B107, Wenjie Fang nous parlera de : Aspects énumératifs et bijectifs des cartes combinatoires Résumé : Les cartes combinatoires, étant un modèle riche, portent plusieurs aspects : algébrique, géométrique, bijective, ... Dans cet exposé, je présente un ensemble de résultats et de connexions dans le domaine de l'énumération des cartes, obtenus à travers des aspects différents. Nous verrons comment utiliser les outils algébrique, comme caractères du groupe symétrique et équations fonctionnelles, à énumérer les cartes. Nous verrons aussi comment étudier les autres objets dans la combinatoire, ici les intervalles du treillis de Tamari, à travers de l'aspect bijectif des cartes. À demain, Thierry

1 0

Seminaire CALIN a 14h demain
by Thierry Monteil 22 Jan '18

22 Jan '18

Bonjour, demain mardi 23 janvier 2018 à 14h00 en B107 (après l'AG qui aura lieu à midi dans l'amphi gauche de l'IUT de Villetaneuse), Vincent Jugé nous parlera de : Uniform generation of infinite concurrent runs: the case of trace monoids. Résumé : We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. Using trace monoids as concurrency models, we will first focus on the notion of a uniform distribution on infinite traces in general and on the simulation of such a distribution. Then, we will introduce our algorithm, which aims at simulating a uniform distribution in a distributed context. This algorithm outputs on-the-fly approximations of a theoretical infinite run, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm, and the execution of the algorithm only involves distributed computations, provided that some - costly - precomputations have been done. This presentation is based on a joint work with Samy Abbes. À demain, Thierry

1 0

Seminaire CALIN a 14h aujourd'hui
by Thierry Monteil 16 Jan '18

16 Jan '18

Bonjour, Aujourd'hui mardi 16 janvier 2018 à 14h00 en B107, Pierre Rousselin nous parlera de : Chute de dimension pour les marches aléatoires sur les arbres aléatoires Résumé : Nous nous intéressons à différents modèles d'arbres aléatoires et aux marches aléatoires sur les sommets de tels arbres. Dans le cas où la marche aléatoire est transiente, la marche part presque sûrement vers l'infini en empruntant un rayon aléatoire. La loi de ce rayon est appelée la mesure harmonique sur le bord de l'arbre. Un phénomène de chute de dimension se produit : cette mesure harmonique est presque sûrement concentrée sur une partie petite (au sens de la dimension de Hausdorff) du bord de l'arbre. Autrement dit, les trajectoires de la marche aléatoires sont presque sûrement comprises dans un sous-arbre beaucoup plus fin que l'arbre original. Cette théorie a été initiée par Russel Lyons, Robin Pemantle et Yuval Peres dans les années 1990. Plus récemment, Nicolas Curien, Jean-François Le Gall, puis Shen Lin ont étudié ce phénomène sur un autre modèle d'arbres aléatoires. Nous rappellerons leurs résultats et discuterons des généralisations (https://arxiv.org/abs/1708.06965 et https://arxiv.org/abs/1711.07920) sur lesquelles nous avons travaillé. Desole pour le retard de l'annonce, Thierry

1 0

Seminaire Calin demain mardi 9 janvier
by Thierry Monteil 08 Jan '18

08 Jan '18

Bonjour et bonne année, demain mardi 9 janvier 2018 à 14h00 en B107, Jordan Emme nous parlera de : Produits de matrices aléatoires et application arithmétique Résumé : Dans un travail en commun avec Pascal Hubert, nous étudions les lois limites de certains produits de matrices et en donnons une application arithmétique: On note s_2 la fonction somme des chiffres en base 2 et on considère, pour tous paramètres entiers a et d, la densité asymptotique mu_a(d) des ensembles d'entiers n tels que s_2(n+a)-s_2(n)=d. Pour tout a, mu_a est une mesure de probabilité sur Z. On démontre que pour toute mesure invariante ergodique sur {0,1}^N, et pour toute suite d'entiers (a_n) dont les décompositions en binaire décrivent les préfixes d'un point générique de cette mesure, mu_{a_n} vérifie un théorème de type limite centrée. Ce résultat est obtenu en calculant les moments de mu_{a_n} qui sont donnés par des produits de matrices aléatoires. Une session false beliefs est envisageable par la suite ! Note: le programme complet du séminaire se trouve sur la page http://lipn.univ-paris13.fr/~banderier/Seminaires/ À demain, Thierry

1 0

Seminaire Calin cet apres-midi
by Thierry Monteil 21 Nov '17

21 Nov '17

Bonjour, cet après-midi, mardi 14 novembre 2017 à 14h00 en B107, Michaël Rao nous parlera de : Recherche exhaustive des pentagones convexes pavant le plan Résumé : Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties: la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus. À tout à l'heure et bon appétit, Thierry

1 1

Seminaire Calin demain
by Thierry Monteil 16 Oct '17

16 Oct '17

Bonjour, demain mardi 29 novembre 2016 à 14h00 en B107, Olivier Bodini nous parlera de : Une analyse asymptotique des polyominos digitalement convexes. Résumé : Dans cet exposé, nous montrerons comment des techniques élémentaires (transformées de Mellin) en combinatoire analytique permettent d'obtenir des résultats assez surprenants sur les polyominos. En particulier, si l'on savait correctement énumérer les polyominos digitalement convexes, nous saurions si l'hypothèse de Riemann est vraie ! Par ailleurs, le GT CIP ("Combinatoire, Informatique et Physique") se réunit régulièrement le mardi matin à 10h30 et tous les membres de l'équipe CALIN sont invités à venir participer, discuter, et exposer (certains exposés du séminaire CALIN ont lieu dans cette tranche horaire). Demain matin: - à 10h30, Quoc Hoan Ngo parlera de "Double régularisation des polyzêtas en les multi-indices négatifs et extensions rationnelles (2ème partie)" - à 11h30, Van Chiên Bui parlera de "Développement asymptotique des sommes harmoniques (2ème partie)" A demain, Thierry

1 4

Seminaire CALIN + the combinatoire (false beliefs)
by Thierry Monteil 26 Sep '17

26 Sep '17

Bonjour, ce mardi 26 septembre 2017 à 14h00 en B107, Paul Mercat nous parlera de : Un algorithme pour décider si un ensemble de Meyer substitutif est un coupé-projeté régulier ou non. Résumé : Après avoir introduit ce que sont les quasicristaux, j'expliquai deux façons d'en construire : avec une description substitutive, et par coupé-projection. Le but de cet exposé sera de faire un lien entre ces deux constructions en se restreignant au cas d'un quasicristal de dimension 1 pour simplifier l'exposé. Plus précisément, étant donné une substitution associée à un nombre de Pisot, j'expliquai comment décider si le pavage autosimilaire correspondant peut aussi être décrit par un coupé-projeté régulier. Par ailleurs, le GT CIP ("Combinatoire, Informatique et Physique") se réunit régulièrement le mardi matin à 10h30 et tous les membres de l'équipe CALIN sont invités à venir participer, discuter, et exposer (certains exposés du séminaire CALIN ont lieu dans cette tranche horaire). Demain matin à 10h30 en salle B107, Christian Lavault parlera de "Propriétés des fonctions de Mittag-Leffler". Enfin, suite à la suggestion de Gérard mardi dernier, le séminaire sera suivi d'un thé combinatoire sur le thème "False beliefs in mathematics", ou chacun·e est invité·e à présenter une ou plusieurs croyances fausses en mathématiques (avec une indication simple qui remette les choses en place), une possibilité étant de présenter une réponse à la question: https://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-i… A demain, Thierry

1 0

Seminaire Calin (ATTENTION SALLE D214)
by Thierry Monteil 18 Sep '17

18 Sep '17

Bonjour, demain mardi 19 septembre 2017 à 14h00 en D214, Valentin Bonzom nous parlera de "Triangulations colorées en dimensions 3 et 4". Notez le changement exceptionnel de salle. Résumé : Les triangulations colorées sont des espaces discrets formés par collage de briques élémentaires qui sont elles-mêmes formées de simplexes en dimension d. Ces briques élémentaires sont par exemple des polygones en dimension 2 et incluent les octaèdres en dimension 3. Les triangulations colorées visent ainsi le développement d'une nouvelle théorie qui intègrerait les cartes combinatoires, spécifiques à la dimension 2, dans un cadre théorique en dimension arbitraire. Je présenterai ces objets en expliquant qu'ils peuvent être représentés par des graphes aux arêtes colorées. Cela les rend particulièrement propices à l'analyse combinatoire, dans le but de les classifier combinatoirement à la manière du genre en dimension 2 et de les énumérer. Je définirai une notion généralisant la planarité en dimension supérieure et je présenterai un système d'équations portant sur les fonctions génératrices de triangulations colorées, qui généralise les équations de Tutte/Schwinger-Dyson des cartes. Selon le temps restant et les gouts de l'auditoire, je pourrai présenter des résultats soit en dimension 3 lorsque les briques élémentaires sont homéomorphes à des boules, soit en dimension 4 où il existe des régimes dans les classes d'universalité des arbres, des cartes planaires et des arbres de cartes mélangeant les deux. Par ailleurs, le GT CIP ("Combinatoire, Informatique et Physique") se réunit régulièrement le mardi matin à 10h30 et tous les membres de l'équipe CALIN sont invités à venir participer, discuter, et exposer (certains exposés du séminaire CALIN ont lieu dans cette tranche horaire). Demain matin à 10h30 en salle B107, Hoang Ngoc Minh parlera de "Décalage des centres". A demain, Thierry

1 0