Meeting notes 11 04 20

David R discussed his new problem for isomorphism of exponentially large graphs.

He began by describing the gadget description of Cai, Furer, Immerman optimal lower bound on the number of variables for graph identification. This is a construction that provides counter examples to the k-dimensional Weisfeiler-Leman example. In other words it provides sets of graphs for which the k dimensional WL algorithm will take exponential time to distinguish these graphs.

Using the motivation of the CFI constructions, David R asked some questions about distinguishing exponentially large graphs. In this model you can (say) query a vertex of an exponentially large graph.

The W-L algorithm

As explained by Dave B. W-L stands for Weisfeiler-Leman.

First, you must understand cellular algebras, defined as follows. Let <math>V=[n]</math> be the vertices, and define Mat<math>_V</math> be the algebra of <math>n\times n\;\mathbb{C}</math>-valued matrices.

A cellular algebra is a subalgebra of Mat<math>_V</math> (meaning a subset that contains the identity and is closed under linear combinations and multiplication; i.e. is itself an algebra) that is closed under <math>\dagger</math>, and closed under the Hadamard (entrywise) product <math>\circ</math> (also called "freshman multiplication.") It should not only contain the identity <math>I</math> but also the all-ones matrix <math>J</math>, defined by <math>I_{i,j}=\delta_{i,j}</math> and <math>J_{i,j}=1</math>.

Important fact

Any cellular algebra has a standard basis, meaning a collection of <math>R_1,\ldots,R_m</math>, where <math>m</math> is the dimension of the algebra and each <math>R_i</math> is a 0-1 matrix. Further <math>J = \sum_{i=1}^m R_i</math> so the elements of <math>R_i</math> equal to 1 form a partition of the <math>n^2</math> entries of a matrix. Note that any algebra has a basis, but the 0/1 property is less obvious. We define the cells to be the <math>R_i</math> with only diagonal elements. It turns out that the sum over cells <math>R_i</math> yields <math>I</math>

1-D W-L algorithm

Let <math>A</math> by the adjacency matrix. Then compute the algebra generated by <math>A,I,J</math> and look at its cells. Use this to solve the graph automorphism problem, which asks whether there exists a nonidentity permutation that takes the graph to itself. In others, is <math>Aut(A)</math> nontrivial?

How it works

Define <math>Z(\text{Aut}(A)) = \{ M: MP=PM \forall P\in\text{Aut}(A) \}</math>. Hope that <math>Z(\text{Aut}(A)) = \langle A,I,J\rangle</math>. (Note that we always have <math>Z(\text{Aut}(A)) \supset \langle A,I,J\rangle</math>.) If this were true, then we could check whether the automorphism group is trivial, since <math>\text{Aut}(A)=\{e\} \Leftrightarrow Z(\text{Aut}(A)) = \text{Mat}_V</math>. In this case, we say that the subalgebra <math>\langle A,I,J\rangle</math> is Schurian.

In the <math>k^{\text{th}}</math> dimension!

Let <math>W=\langle A,I,J\rangle</math>, and let <math>V</math> be the symmetric subspace of

<math>W^{\otimes k}</math>.