Combinatorics Seminar 2017

Speaker: Wenxue Du (杜文学), Anhui University

Date: Sat, Jul 15, 2017

Time: 14:30 - 16:30

Venue: Middle Meeting Room

Title: The Graph Isomorphism Problem


Let $G$ and $H$ be two simple graphs. A bijective map $\phi:V(G)\rightarrow V(H)$ is called an isomorphism between $G$ and $H$ if $\phi(v_i)\phi(v_j)\in E(H)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$, and $G$ and $H$ are said to be isomorphic if there exists such a map. In the case that $G = H$, we say $\phi$ an automorphism of $G$ and denote the group consisting of automorphisms of $G$ by $\mathrm{Aut}\hspace{0.5mm} G$. One of key steps in determining whether or not $G$ is isomorphic to $H$ is to characterize the structure of the action of $\mathrm{Aut}\hspace{0.5mm} G$ on $V(G)$. By means of bipartite graphs $\{ [\Pi^\ast (u), \Pi^\ast (v)] : u,v \in V(G)\}$ and other combinatorial constructions alike, we can reduce the problem of determining the partition $\Pi_G^\ast$, composed of orbits of $\mathrm{Aut}\hspace{0.5mm} G$, to that of working out the family of partitions $\{ \Pi^\ast_v : v \in V(G) \}$, where $\Pi^\ast_v$ is comprised of orbits of the stabilizer $( \mathrm{Aut}\hspace{0.5mm} G )_v$.

On the other hand, we have a permutation group $\mathrm{Aut}\hspace{0.5mm} U$ for each subspace $U \subseteq \mathbb{R}^n$, which is composed of those permutations in $S_n$ for each of which $U$ is invariant. Then $\mathrm{Aut}\hspace{0.5mm} G = \cap_{\lambda \in \mathrm{spec} \hspace{0.3mm} \mathbf{A}(G) } \mathrm{Aut}\hspace{0.5mm} V_{\lambda}$, where $V_{\lambda}$ is the eigenspace of $\mathbf{A}(G)$ corresponding to $\lambda$. Accordingly, we can obtain the structure of $\mathrm{Aut}\hspace{0.5mm} G$ action by means of the structure of $\mathrm{Aut}\hspace{0.5mm} V_{\lambda}$ action, $\lambda \in \mathrm{spec} \hspace{0.3mm} \mathbf{A}(G)$. The latter can be obtained by analyzing a decomposition of $V_{\lambda}$ resulted from the division of $V_{\lambda}$ by subspaces $\{ \mathrm{proj} [V_{\lambda}] ( \pmb{e}_v )^{\perp} : v \in V(G) \}$, where $\mathrm{proj} [V_{\lambda}] ( \pmb{e}_v )^{\perp}$ stands for the orthogonal complement of $\mathrm{proj} [V_{\lambda}] ( \pmb{e}_v )$ in $V_{\lambda}$. As an application, we devise a new algorithm solving the Graph Isomorphism problem in time $n^{ O( \log n ) }$, which is equal to $e^{ O\left( \log^2 n \right) }$.