Combinatorics and Algorithms

Computing defines, studies and manipulates finite or discrete structures by means of algorithms. A natural and important formal framework for this activity is combinatorics. Thus the research undertaken in this team intermingles computing and combinatorics: many algorithms and their associated analyses and proofs use combinatorial objects, constructions and analyses and, in the other direction, these algorithms are the source of new combinatorial problems.

Among the most frequently used objects or structures are words, trees, graphs, maps, paths, permutations, partitions and generating functions.

Classical operations and manipulations defined and studied are: bijections, codes, enumeration, random generation, drawing (visualisation), colouring and more generally relabelling.

The development of algorithms, that is effective procedures allowing us to answer questions or to calculate the values of functions in a finite number of steps, is particularly active in the following areas:

• random generation whose aim is to generate combinatorial objects according to a given distribution rather than exhaustively,
• computer algebra,
• communication problems in interconnection networks,
• modelling and study of problems arising in distributed systems,
• probabilistic algorithms.

Algorithms give rise to combinatorial problems of very different natures:

• enumeration of objects can allow the exact or average analysis of algorithms,
• efficient representation and manipulation of a variety of mathematical objects (graphs, knots, groups, formal series),
• explicit computations on these objects,
• finding correspondences between these objects by means of bijections,
• purely combinatorial study of the properties of certain objects or families of objects such as words, trees, sandpiles or graphs.

Research themes:

• Enumerative and algebraic combinatorics
• Keywords: enumeration, random generation, generating functions, bijections, maps, groups, symmetric and quasi-symmetric functions.
• Graphs and Applications
• Keywords: Routing in networks, compact data structures, Hamiltonism, colouring, transmision index.
• Distributed Algorithms