http://www.dagstuhl.de/16241

June 12 – 17 , 2016, Dagstuhl Seminar 16241

Graph Polynomials: Towards a Comparative Theory

Organizers

Jo Ellis-Monaghan (Saint Michael's College – Colchester, US)
Andrew Goodall (Charles University – Prague, CZ)
Johann A. Makowsky (Technion – Haifa, IL)
Iain Moffatt (Royal Holloway University of London, GB)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 6, Issue 6 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]

Summary

The intent of this 5-day Seminar was to develop a general theory of 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. 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. 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 now urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory.

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 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: the Seminar initiated work on creating a general theory that will bring them together under one family. The process of developing such a theory of graph polynomials should expose 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 provided 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. During the Seminar the participants were offered a conspectus of the broad area of graph polynomials. The view was confirmed that a synthetic approach is needed in order to see the wood for the trees. The discussions and collaborations initiated at the workshop promise well for the development of a unified theory of graph polynomials. This Seminar represented a convincing beginning, and, hopefully, similar meetings in future will further the envisaged project.

In the light of our stated goals, the Seminar provided ample time for discussion groups and tutorials. The participants (44) of the Seminar included some of the leading experts in combinatorics, knot theory, matroid theory and graph polynomials from Europe, the Americas, Asia and Australia. The composition of participants was both age and gender balanced with a quarter of the participants being women. The younger researchers (more than a quarter of the participants) profited from intense contacts and discussions with their more experienced colleagues. An inspiring problem session brought about particular directions for further research.

License
  Creative Commons BY 3.0 Unported license
  Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt

Classification

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

Keywords

  • Graph Polynomials
  • Second Order Logic
  • Graph Colourings
  • Graph Homomorphisms
  • Graph Invariants
  • Matroid Invariants
  • Counting Functions
  • Complexity
  • Topological Graph Theory

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

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.

NSF young researcher support