Le Laboratoire d’Algèbre, de Combinatoire et d’Informatique Mathématique (LACIM) est un centre de recherche institutionnel de l’Université du Québec à Montréal (UQAM) regroupant chercheurs, stagiaires postdoctoraux et étudiants dont les grands thèmes de recherche puisent leurs origines dans la combinatoire et ses liens avec l’algèbre et l’informatique. Le LACIM est aussi l’un des laboratoires associés du Centre de Recherche Mathématiques (CRM).

La combinatoire a pour but de développer la compréhension et l’analyse des propriétés de structures finis ou discrètes. La combinatoire est ainsi l’un des champs fondamentaux des mathématiques, surtout depuis la 2^e guerre mondiale où elle a connu un véritable essor avec le développement de l’informatique, de la théorie des représentations, de la théorie des graphes, de la théorie des groupes finis, de la physique statistique et la théorie des quantas. La combinatoire s’affirme donc comme un domaine profond et riche dont les applications sont très nombreuses en mathématiques (notamment en algèbre, topologie, géométrie et probabilité) et informatique (notamment en analyse et production d’algorithmes), mais aussi en physique (notamment via la théorie de la représentation combinatoire), en linguistique (hiérarchie de Chomsky), en Chimie combinatoire et biologie évolutive ou encore en physique statistique. Les questions posées par ce domaine sont très intuitives et proviennent souvent de problèmes concrets tels que : comment paver un espace avec des objets simples afin de le découper et le comprendre; comment décrire efficacement le chemin parcouru dans un espace donné (par exemple l’espace-temps) par un objet (une particule); peut-on décrire proprement l’évolution des espèces, des langues; Combien de couleurs faut-il au minimum afin de dessiner une carte du monde en coloriant chaque pays afin qu’il se distingue? Cette dernière question a mené par exemple au problème des quatre couleurs énoncé en 1852 par un cartographe anglais et résolu en 1976 par Appel et Hanken grâce à un mélange de théorie des graphes, d’informatique mathématique et d’expérimentation mathématique assistée par ordinateur. Comme pour le problème des quatre couleurs où les graphes ont joué un rôle primordial, derrière chacune des questions ci-dessus se cache des structures combinatoires (permutations, mots, langages, tableaux, graphes, etc.) dont les propriétés permettent de proposer des réponses à ces question, à la manière d’un corps vivant que l’on décrirait par son squelette, son réseau nerveux et son système sanguin. Un autre exemple est le problème de comprendre l’évolution des espèces : la bio-informatique met au point des modèles combinatoires pour l’analyse et la comparaison de séquences génomiques, afin de décrire le réarrangement de gènes, la reconstruction de séquences ancestrales ou la classification de séquences de virus.

Le LACIM a d’abord fait sa marque en développant la Théorie des Espèces de Structures, qui permet d’unifier et d’approfondir la notion de constructions combinatoires comme celles des arbres, de graphes, de permutations, ou encore de mots. Depuis ses origines, les recherches au LACIM se sont grandement diversifiées. Il est reconnu, sur la scène internationale, comme l’un des principaux pôles de recherche en combinatoire algébrique, combinatoire énumérative et combinatoire des mots; avec en plus des axes de recherches liés à la bio-informatique et à l’analyse d’algorithmes. Le LACIM entretient de nombreuses collaborations avec la plupart des grands centres mondiaux dans ce domaine, particulièrement au Canada, en France et aux États-Unis.

La Chaire de Recherche du Canada en algèbre, combinatoire et informatique mathématique de l’Université du Québec à Montréal et associée au LaCIM.