9
$\begingroup$

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my question is overly naive.

1. My first question is on some of the background Babai assumes about the Weisfeiler-Leman canonical refinement process. On several occasions he remarks that certain regularity properties his proofs exploit come 'for free' as a result of WL refinement. See for example the proof of the basic Design Lemma (especially on page 41 in the linked paper). The intuition goes as "$k$-dimensional WL refinement creates regularity on the scale of $k$ vertices", and if you examine each of his regularity conditions, you will find that they are indeed "local" w.r.t. the dimension of refinement.

This is further supported by this paper by Immerman and Lander, where they prove among other things that any two graphs with the same $k$-dimensional canonical WL refinement agree on all first-order with counting formulas on $k$ variables (where the variables can take values in the vertices of each graph).

However, I haven't been able to see a nice, uniform way in which the regularity results Babai needs follow from this property of $k$-WL. Am I missing something (maybe relevant previous work?)?

2. My second question is a sort of continuation: Babai outlines a way to get the same regularity properties without WL refinement (see the footnote on page 41). I think I got his idea to formally work, as described in section 3.3. of this essay; however it requires tiny ad-hoc arguments for each kind of regularity you want to use. So my question is, if there is no uniform way to prove such regularity statements using WL (i.e. if the answer to my first question is 'no'), then both the WL and non-WL methods require us to look into the details of the current situation, so what's the point of using WL at all? Dispensing of it would make for a more self-contained, first-principles paper.

I guess one reason would be that WL has become a common tool in the study of the GI problem, so the people who have worked in that field are well aware of its magic, and to a large extent it guides the intuition behind many of the proofs?

$\endgroup$
1
  • $\begingroup$ perhaps it might help if you spell out in some detail what kind of regularity Babai needs. $\endgroup$ Jul 3, 2016 at 15:45

1 Answer 1

6
$\begingroup$

Not to toot my own tooting of other people's horns, but you'll find an explanation of k-ary Weisfeiler-Leman (complete with pseudocode) in section 2.5 of my Bourbaki talk on Babai's work (and Luks's, and Weisfeiler-Leman's...), now in the arxiv (in french).

Note: this is what I reconstructed based on what other people said the method did. It works, but experts may find it odd (and then they should tell me).

$\endgroup$
2
  • 3
    $\begingroup$ Could you include a link to the arXiv version of your talk? (I could not find it easily- perhaps it has not yet been uploaded...?) $\endgroup$ Jan 16, 2017 at 22:52
  • 1
    $\begingroup$ In any case, the text is available on Bourbaki's web page, bourbaki.ens.fr/TEXTES/1125.pdf $\endgroup$
    – ACL
    Jan 17, 2017 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.