Laboratoire d'informatique de Paris Nord


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