Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Calin: Combinatorics, ALgorithmics, INteractions

The LIPN has chosen in May 2010 to create a team focused on Combinatorics. The idea was to collect in a unique community the efforts done in different Combinatorics sub-areas, and with different tools, and to open even more our perspective towards thematics at its interface, a programmatic intention evident already from the team acronym, CALIN (Combinatoire, ALgorithmique et INteractions).

The research is organised along two main axes.

First Axis : Analysis of algorithms and combinatorial structures

The first axis concerns the Theory of Algorithms, and their rigorous analysis, mainly performed through the statistical understanding of the arising random structures and their asymptotics.  We investigate all of those combinatorial structures that are multivalent and omnipresent in Theoretical Computer Science: words, with their link to monoid, ring and group theory; graphs and trees, appearing e.g. as search trees, or as networks, or transition structures in automata; random walks and other dynamics on such graphs; partitions and permutations... Our methods are bijective, probabilistic, or arising from an analytic approach through generating functions and singularity analysis, along the research line pioneered by Philippe Flajolet.

Second Axis: Combinatorial Physics

A second axis is oriented towards what could be called ``Combinatorial Physics'', i.e. a cross-fertilisation of fields within Theoretical Physics and Theoretical Computer Science (with a problem--method exchange in both directions), of which a master example is the combinatorics of graphs and diagrams, based on Hopf Algebras, fundamental for the rigorous understanting of the Renormalisation procedure in a family of toy models in Quantum Field Theory.  In such
a subject the synergy of the members of the team is crucial, as competences of Algebra (such as Representation Theory or Lie Groups) and some background of theoretical physics are an essential complement to tools more specific to combinatorics, such as Lyndon words or symmetric functions, along the research line pioneered by Marcel-Paul Schützenberger.