Dagstuhl Seminar 19401
Comparative Theory for Graph Polynomials
( Sep 29 – Oct 04, 2019 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/19401
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)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- Graph operations and neighborhood polynomials : article - Alipour, Maryam; Tittmann, Peter - Zielona Góra : University, 2020 - (Discussiones Mathematicae Graph Theory ; 15 pp.).
- On the Activities and Partitions of the Vertex Subsets of Graphs : article - Dedndreaj, Kristina; Tittmann, Peter - Cornell University : arXiv.org, 2020. - 21 pp..
- Weakly Distinguishing Graph Polynomials on Addable Properties : article - Makowsky, Johann A.; Rakita, Vsevolod - Cornell University : arXiv.org, 2019. - 17 pp..
Schedule
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.
Creative Commons BY 3.0 DE
Jo Ellis-Monaghan, Andrew Goodall, Iain Moffatt, and Kerri Morgan
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.
Jo Ellis-Monaghan, Andrew Goodall, Iain Moffatt, and Kerri Morgan
- José Aliste-Prieto (Universidad Andres Bello - Santiago de Chile, CL) [dblp]
- Nantel Bergeron (York University - Toronto, CA) [dblp]
- Cornelius Brand (Universität des Saarlandes, DE) [dblp]
- Animesh Chaturvedi (Indian Institute of Technology - Indore, IN) [dblp]
- Carolyn Chun (U.S. Naval Academy - Annapolis, US) [dblp]
- Anna De Mier (UPC - Barcelona, ES) [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]
- Delia Garijo (University of Sevilla, ES) [dblp]
- Daniela Genova (University of North Florida - Jacksonville, US) [dblp]
- Emeric Gioan (University of Montpellier & CNRS, FR) [dblp]
- Chris Godsil (University of Waterloo, CA) [dblp]
- Andrew Goodall (Charles University - Prague, CZ) [dblp]
- Krystal Guo (UL - Brussels, BE) [dblp]
- Orli Herscovici (Technion - Haifa, IL) [dblp]
- Hendrik Jan Hoogeboom (Leiden University, NL) [dblp]
- Benjamin Jones (Monash University - Clayton, AU)
- Nataša Jonoska (University of South Florida - Tampa, US) [dblp]
- Louis H. Kauffman (Novosibirsk State University, RU) [dblp]
- Martin Kochol (Bratislava, SK) [dblp]
- Thomas Krajewski (Aix-Marseille Université, FR) [dblp]
- Joseph Kung (University of North Texas - Denton, US) [dblp]
- Sergei Lando (NRU Higher School of Economics - Moscow, RU)
- Bodo Lass (University Claude Bernard - Lyon, FR) [dblp]
- Johann A. Makowsky (Technion - Haifa, IL) [dblp]
- Iain Moffatt (Royal Holloway University of London, GB) [dblp]
- Kerri Morgan (Deakin University - Melbourne, AU) [dblp]
- Steven Noble (Birkbeck, University of London, GB) [dblp]
- Marc Noy (UPC - Barcelona, ES) [dblp]
- Jaeseong Oh (Seoul National University, KR) [dblp]
- James Oxley (Louisiana State University - Baton Rouge, US) [dblp]
- Vsevolod Rakita (Technion - Haifa, IL) [dblp]
- Elena V. Ravve (ORT Braude College - Karmiel, IL) [dblp]
- Guus Regts (University of Amsterdam, NL) [dblp]
- Adrian Tanasa (University of Bordeaux, FR) [dblp]
- Maya Thompson (Royal Holloway University of London, GB)
- Peter Tittmann (Hochschule Mittweida, DE) [dblp]
- Lluis Vena Cros (Charles University - Prague, CZ)
- William Whistler (Durham University, GB)
- José Zamora Ponce (Universidad Andres Bello - Santiago de Chile, CL) [dblp]
Related Seminars
- Dagstuhl Seminar 16241: Graph Polynomials: Towards a Comparative Theory (2016-06-12 - 2016-06-17) (Details)
Classification
- data structures / algorithms / complexity
- networks
- verification / logic
Keywords
- Graph Polynomials
- Graph and Matroid Invariants
- Tutte polynomial
- Topological and Algebraic Graph Theory
