Dagstuhl Seminar 16241
Graph Polynomials: Towards a Comparative Theory
( Jun 12 – Jun 17, 2016 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/16241
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)
Contact
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- Counting Dominating Sets of Graphs - Heinrich, Irene; Tittmann, Peter - Cornell University : arXiv.org, 2017. - 8 pp..
- Density of Zeros of the Tutte Polynomial - Ok, Seongmin; Perrett, Thomas J. - arXiv, 2016. - 11 pp..
- Neighborhood and Domination Polynomials of Graphs : article - Heinrich, Irene; Tittmann, Peter - Berlin : Springer, 2018. - pp.1203–1216 - (Graphs and combinatorics ; 34. 2018, article).
- The Bipartition Polynomial of a Graph : Reconstruction, Decomposition, and Applications - Ok, Seongmin; Tittmann, Peter - Cornell University : arXiv.org, 2017. - 20 pp..
Schedule
The intent of this Dagstuhl Seminar is to develop a general theory of graph polynomials. Graph polynomials have played a key role in combinatorics and its applications ever since the late nineteenth century. They have effected breakthroughs in conceptual understanding and brought together different strands of scientific thoughts. 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. Research in the area of graph polynomials is incredibly active, with new applications and new graph polynomials being discovered each year. However, the consequent plethora of techniques and results now urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory.
The seminar will provide 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. 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 will leverage that paradigm. More critically, experts in the field have recently begun noticing clear resonances among both results and proof techniques for the various polynomials. The species and genera of graph polynomials are diverse, but there are strong interconnections: we will be working towards a general theory that brings them together under one family. The process of developing such a theory of graph polynomials will expose deeper connections, giving great impetus to both theory and applications. The impact on all those fields of science where combinatorial information needs to be extracted and interpreted has immense and exciting potential.
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.
Creative Commons BY 3.0 Unported license
Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt
- Ilia Averbouch (Technion - Haifa, IL) [dblp]
- Spencer Backman (Universität Bonn, DE) [dblp]
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Béla Bollobás (University of Cambridge, GB & University of Memphis, US) [dblp]
- Robert Brijder (Hasselt University - Diepenbeek, BE) [dblp]
- Ada Sze Sze Chan (York University - Toronto, CA)
- Carolyn Chun (Brunel University London, GB) [dblp]
- Bruno Courcelle (University of Bordeaux, FR) [dblp]
- Anna De Mier (UPC - Barcelona, ES) [dblp]
- Holger Dell (Universität des Saarlandes, DE) [dblp]
- Jo Ellis-Monaghan (Saint Michael's College - Colchester, US) [dblp]
- Graham Farr (Monash University - Clayton, AU) [dblp]
- Alex Fink (Queen Mary University of London, GB) [dblp]
- Emeric Gioan (University of Montpellier & CNRS, FR) [dblp]
- Andrew Goodall (Charles University - Prague, CZ) [dblp]
- Gary P. Gordon (Lafayette College - Easton, US) [dblp]
- Krystal Guo (University of Waterloo, CA) [dblp]
- Hendrik Jan Hoogeboom (Leiden University, NL) [dblp]
- Thore Husfeldt (IT University of Copenhagen, DK) [dblp]
- Nataša Jonoska (University of South Florida - Tampa, US) [dblp]
- Louis H. Kauffman (University of Illinois - Chicago, US) [dblp]
- Marsha Kleinbauer (TU Kaiserslautern, DE) [dblp]
- Tomer Kotek (TU Wien, AT) [dblp]
- Joseph Kung (University of North Texas - Denton, US) [dblp]
- Martin Loebl (Charles University - Prague, CZ) [dblp]
- Johann A. Makowsky (Technion - Haifa, IL) [dblp]
- Liz McMahon (Lafayette College - Easton, US)
- Iain Moffatt (Royal Holloway University of London, GB) [dblp]
- Kerri Morgan (Monash University - Clayton, AU) [dblp]
- Ada Morse (University of Vermont, US) [dblp]
- Jaroslav Nešetril (Charles University - Prague, CZ) [dblp]
- Steven Noble (Brunel University London, GB) [dblp]
- Marc Noy (UPC - Barcelona, ES) [dblp]
- Seongmin Ok (Korean Institute for Advanced Study, KR) [dblp]
- James Oxley (Louisiana State University - Baton Rouge, US) [dblp]
- Thomas Perrett (Technical University of Denmark - Lyngby, DK) [dblp]
- Vsevolod Rakita (Technion - Haifa, IL) [dblp]
- Elena V. Ravve (ORT Braude College - Karmiel, IL) [dblp]
- Guus Regts (University of Amsterdam, NL) [dblp]
- Gordon Royle (The University of Western Australia - Crawley, AU) [dblp]
- Benjamin Smith (Royal Holloway University of London, GB) [dblp]
- Peter Tittmann (Hochschule Mittweida, DE) [dblp]
- Martin Trinks (Nankai University - Tianjin, CN) [dblp]
- William Whistler (Durham University, GB)
Related Seminars
- Dagstuhl Seminar 19401: Comparative Theory for Graph Polynomials (2019-09-29 - 2019-10-04) (Details)
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
