4
$\begingroup$

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected graphs with multiple identical connected components, and each connected component also has an automorphism group of its own). These automorphisms induce equivalence relations between $\pi$'s. I am computing a sum $\sum_\pi f(\pi)$ where the function $f$ is constant on each equivalence class of $\pi$'s. The function $f$ is expensive to evaluate, so I want to group equivalent terms in this sum to have fewer terms to deal with.

So I need to divide all maps $\pi$ into a small number of groups $P_i$ so that within each $P_i$ the maps are equivalent up to applying the graph automorphisms. For each $P_i$ I need to know a representative, and its cardinality $n_i$ (so that $\sum n_i=N!$). Now, I imagine that finding the minimal possible number of $P_i$'s is a hard problem (this would be the problem of understanding the structure of double coset space $G_1\backslash S_N/G_2$, where $G_i$ are the automorphism groups of $\Gamma_i$.)

But in practice I don't need the full classification of equivalence classes, I just need that the total number of $P_i$'s be not too large. I am wondering if there is a systematic algorithm which inexpensively produces a rough grouping of terms (say using the simplest connected components), and with more running time produces a slightly better grouping etc. I will then decide myself when to terminate the grouping process and switch to the sum evaluation.

More specific information: My graphs are subject to the condition $N/2+2E<\Delta$, where $N$ and $E$ are the number of nodes and edges and $\Delta=16\div 20$. In particular no connected component has more than 10 nodes, but the total number of nodes can be as much as 40 provided that they are all disconnected. Saving the full $S_N$ in memory and working on it is impractical, but once one separates out fully disconnected single vertices, and other simple connected components, it starts looking practical.

The function $f$ depends on the global structure of the graphs and of the map. It is not a polynomial in the variables $x_{ij}$ that Joshua mentions in his comment below. I doubt it will help, but I will provide more details. One associates a particular $D$-dimensional tensor with each pair of vertices connected by $\pi$. The tensor has $d_i+d_j$ indices where $d_i$ and $d_j$ are the degrees of the vertices. The $f$ is a number obtained by contracting indices of all the tensors along the graph edges.

$\endgroup$
5
  • $\begingroup$ Can you be a bit more specific, e.g. as to the value(s) of N you're interested in, the size of $G_i$, and the nature of the function f? As you point out, the min number of $P_i$ is already $|G_1 \backslash S_N / G_2|$, which in general I would expect to be quite large as a function of $N$... Practially speaking, $S_{10}$ is storable in memory, but $S_{20}$ isn't, so "O(10)" isn't really specific enough. Also, the structure of $f$ could be helpful. e.g., if $f$ is a polynomial in the variables $x_{ij}$ where $x_{ij} = 1$ iff $\pi(i) = j$ and $x_{ij}=0$ otherwise, that might be useful... $\endgroup$ Aug 15, 2013 at 18:49
  • $\begingroup$ What does make you think that the structure of the double coset space is hard in this case? It's a pretty standard computation with permutation groups, doable for groups orders of magnitude bigger than yours. $\endgroup$ Aug 16, 2013 at 3:36
  • $\begingroup$ @Dima Pasechnik I didn't realize that. I see that GAP3 can compute right cosets, and GAP4 double cosets. But I did not know how efficient these realizations are. Do you think they will do for me? $\endgroup$ Aug 16, 2013 at 6:10
  • 1
    $\begingroup$ Why don't you just try computing the double cosets in GAP? My feeling is that if this does not work, then the reason will be that there are too many double coset reps, in which case you are unlikely to be able to complete your calculation by any other method. $\endgroup$
    – Derek Holt
    Aug 16, 2013 at 8:08
  • 2
    $\begingroup$ GAP was sufficient to solve this problem. Thanks to everyone. $\endgroup$ Sep 12, 2013 at 11:42

0

Your Answer

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