Counting Isomorphism Classes of Graphs

Description of the problem

Today, I’d like to count the number of unlabeled simple graphs on $n$ vertices, otherwise known as isomorphism classes of simple graphs on $n$ vertices. I am going to use what is called Burnside’s Lemma.

Counting orbits

When you have an object that consists of $n$ labeled parts, the permutation group $S_n$ acts on the labels by permuting them. If we’d like to remove all of the labels, and count the number of all configurations without labels, we would need to use Burnside’s Lemma. The lemma gives us an effective formula for the number of orbits of a group $G$ acting on a set of configurations $X$. The number of orbits of the action is

\[ |X/G| = \frac{1}{|G|} \sum_{g\in S_n} |X^g| \]

where $X^g=\{x\in X\mid gx=x\}$.

Given an element $g\in G$, the orbit of an element $x\in X$ under repeated action of $g$ is

\[ \mathcal{O} = \{ x, gx, g^2x,\ldots, g^{n-1}x \} \]

where $n$ is the smallest integer with $g^n x = x$. If we can join these configurations into a single configuration, the newly formed configuration is fixed under $g$. We can split the set of all configurations into such orbits: $\mathcal{O}_1,\ldots,\mathcal{O}_\ell$. Then the set of configurations fixed by $g$ will be $2^\ell$. We can rewrite the Burnside Lemma as

\[ |X/G| = \frac{1}{|G|} \sum_{g\in G} 2^{\ell(g)} \]

In our case, our group is $S_n$ and the set $X$ is the set of edges of the largest graph (which is the complete graph $K_n$) one can write on $n$ vertices.

The count

Let us start with the set of edges of the complete graph:

(defun complete-graph (n)
  (loop for i from 1 below n
        append (loop for j from (1+ i) to n
                     collect (list i j))))

COMPLETE-GRAPH

A permutation on $n$-letters in this context is a specific ordering of the numbers from 1 to n. The list of all permutations is given by

(defun all-permutations (n)
  (if (= n 1)
      (list (list 1))
      (mapcan (lambda (seq)
                (let ((res-list nil))
                  (dotimes (i n res-list)
                    (push (nconc (subseq seq 0 i)
                                 (cons n (subseq seq i)))
                          res-list))))
              (all-permutations (1- n)))))

ALL-PERMUTATIONS

Next, we calculate the orbit of an edge under the action of a permutation

(defun edge-orbit (perm xs &optional carry)
  (let ((ys (sort (mapcar (lambda (x) (elt perm (1- x))) xs) #'<)))
    (if (member xs carry :test #'equal)
        carry
        (edge-orbit perm ys (append carry (list xs))))))

EDGE-ORBIT

Now that we have the orbit, we can calculate the number of orbits:

(defun number-of-orbits (perm edges &optional (number 0))
  (if (null edges)
      number
      (let* ((ys (edge-orbit perm (car edges)))
             (zs (set-difference edges ys :test #'equal)))
        (number-of-orbits perm zs (incf number)))))

NUMBER-OF-ORBITS

And finally, the Burside lemma:

(defun fact (n)
  (if (or (zerop n)
          (= n 1))
      1
      (* n (fact (1- n)))))

(defun experiment (n)
  (let ((sum 0)
        (edges (complete-graph n)))
    (dolist (perm (all-permutations n) (/ sum (fact n)))
      (incf sum (expt 2 (number-of-orbits perm edges))))))

FACT
EXPERIMENT

Let us test:

(loop for i from 1 to 10 collect (experiment i))

(1 2 4 11 34 156 1044 12346 274668 12005168)

This is A000088 from The On-Line Encyclopedia of Integer Sequences.

An analysis

The complexity is really bad. Luckily, there is a better way of counting. In the case the actions of $S_n$, the shape of a permutation as a product of disjoint cycles, determines the size of the orbit. So, instead of doing the sum for each permutation, we can do it per each shape then multiply the number $2^\ell$ by the number of permutations sharing the same shape. But I’ll do that at another time.