https://www.dagstuhl.de/19401

29. September – 04. Oktober 2019, Dagstuhl-Seminar 19401

Comparative Theory for Graph Polynomials

Organisatoren

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)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.