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 erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 9, Issue 9 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]

Summary

This 5-day Seminar built on the previous Dagstuhl Seminar 16241 together with several intervening workshops on graph polynomials, particularly those associated with William Tutte's Centenary, to advance an emerging comparative theory for graph polynomials. Graph polynomials have played a key role in combinatorics and its applications, having effected breakthroughs in conceptual understanding and brought together different strands of scientific thought. For example, the characteristic and matching polynomials advanced graph-theoretical techniques in chemistry; and the Tutte polynomial married combinatorics and statistical physics, and helped resolve long-standing problems in knot theory. The area of graph polynomials is incredibly active, with new applications and new graph polynomials being discovered each year. However, the resulting plethora of techniques and results urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory and unified approaches to streamline proofs and deepen understanding.

The Seminar provided a space for the cross-fertilization of ideas among researchers in graph theory, algebraic graph theory, topological graph theory, computational complexity, logic and finite model theory, and 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 workshop leveraged that paradigm. More critically, experts in the field have recently begun noticing strong resonances in both results and proof techniques among the various polynomials. The species and genera of graph polynomials are diverse, but there are strong interconnections: in this seminar we worked towards a general theory that brings them together under one family. The process of developing such a theory of graph polynomials exposes deeper connections, giving great impetus to both theory and applications. This has immense and exciting potential for all those fields of science where combinatorial information needs to be extracted and interpreted.

The seminar was roughly organized according to the following themes:

  • Unification: General frameworks for graph polynomials including meta-problems, K-theory, Second Order Logic, and Hopf algebras.
  • Generalizations: Polynomial invariants for graphs with added structure (e.g. digraphs, ribbon graphs) or more general "underlying" combinatorial structures (e.g. matroids, Delta-matroids).
  • Distinction: Distinguishing power of graph invariants (equivalence and uniqueness up to isomorphism with respect to a given graph polynomial, interrelations among graph polynomials, properties of graph polynomials).
  • Applications: Applications of graph polynomials in other disciplines (e.g. self-assembly, sequencing, quantum walks, statistical mechanics, knot theory, quantum Ising model).
  • Conjectures: Breakthrough conjectures (outstanding open problems whose resolution would have a broad impact on the understanding of graph polynomials).
  • Complexity: Computational complexity and computational methods.
Summary text license
  Creative Commons BY 3.0 Unported license
  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.