https://www.dagstuhl.de/19401

September 29 – October 4 , 2019, Dagstuhl Seminar 19401

Comparative Theory for Graph Polynomials

Organizers

Jo Ellis-Monaghan (Saint Michael's College – Colchester, US)
Andrew Goodall (Charles University – Prague, CZ)
Iain Moffatt (Royal Holloway University of London, GB)
Kerri Morgan (Deakin University – Melbourne, AU)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule (Upload here)

(Use seminar number and access code to log in)

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Jo Ellis-Monaghan, Andrew Goodall, Iain Moffatt, and Kerri Morgan

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity
  • Networks
  • Verification / Logic

Keywords

  • Graph Polynomials
  • Graph and Matroid Invariants
  • Tutte polynomial
  • Topological and Algebraic Graph Theory

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.