Head of Department: András Sebö
The teams, their permanent members, their main
themes
Charles Payan, Mireille Dupraz,
Denise Grenier, Nguyen Huy Xuong
Discrete Mathematics in teaching and the underlying
combinatorial questions
Myriam Preissmann, Claude Benzaken,
Frédéric Maffray, Sylvain Gravier
Graph coloring, perfect graphs, domination, cuts
András Sebö, Wojciech Bienia, Michel Burlet
Combinatorial structures (matroids, matchings, and
generalizations), multiflows, polyhedra, min-max theorems
Gerd Finke, Nadia Brauner
Scheduling, problème d'implantation; long term
coopertion with Renault and Péchiney
|
|
Scientifics Operations |
|
|
|
|
|
|
|
Discrete Mathematics, Graph Theory, Cobinatorics: these terms have almost become synonyms, and they will be used as such on this page. Nevertheless, on the pages of our department's six teams, using one of these terms rather than another may represent methodological differences or different interests.
Do these words refer to the mathematical discipline dealing with discrete or finite structures? Doesn't Combinatorial Topology deal with continuous topological spaces? As for Combinatorial Set Theory, doesn't it deal with large cardinals? Certainly, Discrete Mathematics are tied to these two adjectives, but nowadays the term "Combinatorics" refers rather to a certain type of reflexion.
Discrete Mathematics, Graph Theory, Cobinatorics: what is sure, is that the collection of elementary puzzles that these words used to refer to more than half a century ago has become a domain of Mathematics and Theoretical Computer Science of its own. In most developed countries it is now recognized as such. László Lovász, in the preface to the first edition of his book "Combinatorial Problems and Exercises", in 1979, wrote:
"... It is often forcefully stated that Combinatorics is a collection of problems, which may be interesting in themselves but are not linked and do not constitute a theory ... In my opinion, Combinatorics is growing out of this early stage. There are techniques to learn ... There are branches which consist of theorems forming a hierarchy and which contain central structure theorems forming the backbone of study ... There are notions abstracted to many non-trivial results, which unify large parts of the theory ..."
Among the research topics of our department we find several of those techniques and notions: algebraic, geometric, those from mathematical programming, from Game Theory, from Operations Research, etc.
About the aims of our research, one can find here some purely theoretical themes, guided by the researchers' aestehtics sense, and linked to the internal development of the theory, as well as themes motivated by applications, for example in Computer Science, in Operations Research, or in the teaching of Mathematics. The combinatorial objects on which we work are graphs or hypergraphs, ordered sets, matrices, matroids, polyhedra, or various other mathematical objects. Our research is interested in these objects either per se or as toolds to use.
Some people consider discrete Mathematics as the domain of Mathematics whose ain is to give the theoretical foundations of Computer Science. But instead of going on defining Discrete Mathematics formally, we invite you rather to do a few steps in Graph Theory, accompanied by two members of our department, Sylvain Gravier and Frédéric Maffray of the "Graphs" team.
A mathematician's work is oftentimes individual, but it is also desirable to add the competence of various persons with different cultures:
Our various research themes do not necessarily respect the boundaries between the teams . The names only show the main orientation, which does not impede for example the "Graphs" team from developing optimization algorithms in graphs, or persons from the "CASM" team from doing research in graph theory. Many results are done in collaboration between members of different teams.
Our seminars are organized on an informal basis. We usually have one or two seminars a week:
We organize international mini-colloquia, exploiting the presence of sabbatical visitors, or of guests on UJF or INPG or CNRS fellowships, to which we can add short term visitors. Grenoble has become one of the international centers in Discrete Mathematics, inspiring and exploring various research themes.