19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

Weisfeiler-Leman stabilisation and the graph isomorphism problem

Presented by Mr. Brendan DOUGLAS
Type: Oral presentation
Track: Association Schemes

Content

The Weisfeiler-Leman (WL) method takes as input an arbitrary graph $\Gamma$, and returns the minimal coherent algebra containing the basis relations of $\Gamma$ (e.g. the set of edges and non-edges). We will discuss some well-known properties of a common higher-dimensional generalisation of this method, the $k$-dim WL method, in particular with respect to its application to the graph isomorphism problem (GI). After describing some properties of the known families of `counterexample' graphs, we will introduce a generalisation to the $k$-dim WL method, involving an initial canonical decomposition of the graph, and discuss properties of potential counterexamples to this extended WL method. The goal of this work is simply to investigate the possibility that a variant of the WL method might be used to solve GI.

Place

Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

More