The Weisfeiler-Leman algorithm from a coalgebraic perspective

Moerman, J. (Speaker)

Activity: Talk or presentation types › Talk or presentation (not at a conference) › Academic

Description

This talk is about the Weisfeiler-Leman algorithm. This is an efficient algorithm to colour the vertices (and edges) of a graph in a certain way. It is used as an efficient heuristic to decide graph isomorphism and it was even long thought that it might provide a polynomial algorithm for graph isomorphism (it does not). It was recently observed that this algorithm fits the abstract theory of coalgebraic minimisation. I will explain this connection to coalgebra in detail. However, the real “power” of the WL-algorithm lies in the k-dimensional generalisation and this is harder to relate to coalgebra. We want to understand this from a coalgebraic perspective too, with the hope of bringing results from graph theory to the theory of coalgebra.
The research is work in progress. It is joint work with Tobias Kappé and Thorsten Wißmann.

Period	23 Aug 2023
Event title	Network Types, Coalgebras, Semantics in NL
Event type	Seminar
Conference number	4
Location	Utrecht, NetherlandsShow on map
Degree of Recognition	National