Comparative Theory for Graph Polynomials

Motivation

The study of graph polynomials has become increasingly active, with new applications and new graph polynomials being discovered each year. The genera of graph polynomials are diverse, and their interconnections are rich. Experts in the field are finding that proof techniques and results established in one area can be successfully extended to others. From this, a general theory is emerging that encapsulates the deeper interconnections between families of graph polynomials and the various techniques, computational approaches, and methodologies applied to them.

The overarching aim of this 5-day Dagstuhl Seminar is to exploit commonalities between polynomial invariants of graphs, matroids, and related combinatorial structures. Model-theoretic, computational and other methods will be used in order to construct a comparative theory that collects the current state of knowledge into a more cohesive and powerful framework.

The focus of this seminar is to investigate problems identified as being key components in the development of such a comparative theory, which will involve:

• Broadening the scope of general frameworks for graph polynomials that arise from Hopf algebras;
• Determining how existing computational approaches that have been successfully applied to some families of graph polynomials can be extended to a broad “computational toolbox” for graph polynomials in general;
• Connecting the framework of graph polynomials arising from invariants definable in Second- Order Logic (SOL) (and of partition functions with colouring and general SOL predicates) with other recent approaches towards a unified theory of graph polynomials;
• Synergising the efforts of researchers in matroid theory and in graph polynomials, in regard to recent advances in matroid theory that have arisen from the field of graph polynomials;
• Developing methods to compare the distinguishing power of graph polynomials, that is, the extent to which they uniquely determine objects in their domain and the extent to which two polynomials encode the same information. While the seminar will include scheduled talks, greater emphasis will be given to breakout sessions, where interdisciplinary groups will work on research problems related to the above.