1
$\begingroup$

Problem: describe classes of automorphism for the following collection of graphs.

Let $\mathbb{F}$ be a finite field of order $q$; then the vertex set V is defined as $V = \{(x,y) : x\in\mathbb{F},y\in\mathbb{F}\}$; adjacency is defined as follows: there is an arc from $(x_1,x_2)$ to $(y_1,y_2)$ iff $x_2 + y_2 = x_1^m y_1^n$, where $1\le m,n\le q-1$.

Clearly, $|V|=q^2$, and the number of arcs is about $q^3$. Even for $q=17$ the problem of sorting all $(q-1)^2$ graphs corresponding to possible values of $m$ and $n$ becomes computationally hard. I've managed to obtain explicit formulas for the number of 2- and 3-cycles. So I first sort these graphs out by these parameters: this is done immediately. Then, by their diameter, then by their characteristic polynomial, then by the number of 4-cycles (this is done by brute-force). Only after that I'm checking them directly for isomorphism.

Are there any other invariants that are easy to compute, so that I could separate the $(q-1)^2$ as close to isomorphic classes as possible before actually starting to check them for isomorphism directly. Would the Laplacian spectrum or something like this be "cheap" to compute?

Improve this question
$\endgroup$
4
  • $\begingroup$ If I'm not mistaken, your graph is regular (for each point $(x_1,x_2)$ and each $y_1\in \mathbb{F}$ there is a unique $y_2$ such that $(x_1,x_2)$ is joined to $(y_1,y_2)$, so that the graph is $q$-regular), so the Laplacian matrix differs from the adjaceny matrix only by a scalar matrix. This means the characteristic polynomials of the adjacency matrix and Laplacian matrix are the same after a change of variables $x\mapsto x+ a$ for some $a$. Thus you won't get any new information by looking at the Laplacian matrix. (It would clearly be roughly as fast to compute as the characteristic poly) $\endgroup$
    – Jack Huizenga
    Commented Oct 6, 2012 at 5:34
  • $\begingroup$ Clear. Thank you. Also it appears that if any two such graphs (not necessarily isomorphic) have equal number of 4-cycles, then the numbers of 5- and 6-cycles are also equal. $\endgroup$
    – azazello
    Commented Oct 6, 2012 at 6:05
  • $\begingroup$ Once you've specified the characteristic polynomial does specifying the number of 4-cycles actually cut things down at all? I'd think that since powers of the adjacency matrix count (paths) there would be nothing further to gain by looking at cycles. $\endgroup$
    – Jack Huizenga
    Commented Oct 6, 2012 at 6:19
  • $\begingroup$ How are you testing for isomorphism? Sorting $16^2$ graphs of order $17^2$ by isomorphism type is an easy problem. $\endgroup$
    – Brendan McKay
    Commented Oct 6, 2012 at 7:24

2 Answers 2

Reset to default
2
$\begingroup$

Maybe there is a problem with processing of digraphs in sage. nauty takes 0.07 seconds to canonically label each of the graphs $(17;1,3)$ and $(17;3,1)$. They are indeed isomorphic. This translates to 20 seconds for sorting all $16^2$ graphs (and probably some pre-preprocessing can cut that down a bit).

The automorphism group of these two graphs has 94 orbits and order $2^{52} 3^{51}$. I guessed there would be fewer orbits than that.

It seems to scale ok too. Graph $(37;1,3)$ takes 18 seconds, so that size would take about 6 hours altogether.

Feel free to be in touch off-list. bdm(at)cs.anu.edu.au

Improve this answer
$\endgroup$
-1
$\begingroup$

2 Jack: Counting 4-cycles after char poly actually does refine these graphs into smaller groups further down. It seems like counting $k$-cycles for $k\ge 5$ after counting 4-cycles doesn't make much sense.

2 Brendan: I'm using the internal facility of sage (an open source project encompassing GAP, Maxima and other open source math-related projects wrapped into a Python framework). I very much believe it's based on the same ideas from your paper that nauty is. So it can't be much worse. Checking the underlying looped undirected graphs obtained by sage's graph.to_undirected() is indeed an easy problem. However even checking whether a pair of graphs corresponding to parameters $(m,n) = (1,3)$ and $(m,n) = (1,3)$ for $q=17$, are isomorphic to each other, proves to be quite hard.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I meant $(m,n) = (1,3)$ and $(m,n) = (3,1)$. No, as I said counting 4-cycles after char poly's does refine subcollections of possibly isomorphic graphs. For a long time I had a conjecture that $G(q,m,n)$ and $G(q,n,m)$ are always isomorphic (well, at least they have the same number number of $k$-cycles for any natural $k$). But that turns out to be false. Other than that I can't say much. $\endgroup$
    – azazello
    Commented Oct 6, 2012 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .