12.06.16 - 17.06.16, Seminar 16241

Graph Polynomials: Towards a Comparative Theory

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.


The intent of this Dagstuhl Seminar is to develop a general theory of graph polynomials. Graph polynomials have played a key role in combinatorics and its applications ever since the late nineteenth century. They have effected breakthroughs in conceptual understanding and brought together different strands of scientific thoughts. The characteristic and matching polynomials advanced graph-theoretical techniques in chemistry; the Tutte polynomial married combinatorics and statistical physics, and helped resolve long-standing problems in knot theory. Research in the area of graph polynomials is incredibly active, with new applications and new graph polynomials being discovered each year. However, the consequent plethora of techniques and results now urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory.

The seminar will provide conditions ripe for cross-fertilization of ideas among researchers in graph theory and topological graph theory, in logic and finite model theory, and in current biocomputing and statistical mechanics applications. There is a long history in this area of results in one field leading to breakthroughs in another when techniques are transferred, and this seminar will leverage that paradigm. More critically, experts in the field have recently begun noticing clear resonances among both results and proof techniques for the various polynomials. The species and genera of graph polynomials are diverse, but there are strong interconnections: we will be working towards a general theory that brings them together under one family. The process of developing such a theory of graph polynomials will expose deeper connections, giving great impetus to both theory and applications. The impact on all those fields of science where combinatorial information needs to be extracted and interpreted has immense and exciting potential.