My recollection is that some people were defining "n-transitive" graphs as graphs that had the n-arc isomorphism property but *not* the (n+1) property. This is why big complete graphs (and also big cyclic graphs) are not counterexamples. Notice that K5 (for instance) has the property for *all* n. For n from 1 to 4, all the arcs are isomorphic. For larger n, there are no such arcs ... so they are still all isomorphic. Question: are there any other problematic classes of graphs, besides the complete graphs and the cycles? On Sat, Mar 6, 2010 at 5:33 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
I ought to add that it's not immediately obvious the permutation group and graph isomorphism problems are completely equivalent: on graphs there is the extra constraint that a chains from vertex 1 to n, and 3 to n+2, imply chain from 2 to n+1. But this could only further restrict the possible symmetry group; I don't know whether in practice it actually does so.
Maybe Norman Biggs' book has something to say about such matters? WFL
On 3/6/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
See http://eom.springer.de/t/t093800.htm, which cites P.J. Cameron, "Finite permutation groups and finite simple groups" Bull. London Math. Soc. , 13 (1981) pp. 1–22 .
Presumably (Weiss 1974) was a weaker precursor of this result, which lowers the bound from 7 to 3 --- with the exception of four Mathieu groups, and the alternating and symmetric groups.
WFL
On 3/6/10, Tom Karzes <karzes@sonic.net> wrote:
Wouldn't a complete graph with k nodes be n-arc symmetric for any n less than k?
Tom
I've been recently doing research on highly symmetric tilings of surfaces, which led to learning of an interesting theorem in graph theory (Weiss, 1974):
Define a graph G be as a set V of nodes each pair of which either is or is not connected by an edge. We identify the pair of nodes with the edge.
Let an n-arc on G be defined as a sequence of distinct nodes v_j, 0 <= j <= n, such that {v_(j-1),v_j} is an edge for 1 <= j <= n.
Define a graph to be "n-arc symmetric" if, for any n-arcs A and B of G, there is a graph isomorphism G -> G taking A onto B.
Theorem: If G is n-arc symmetric, then n <= 7.
Anyone know anything about this theorem? The only write-up I could find is the original paper, in German, not a language I'm strong in:
Weiss, R. M. "Über s-reguläre Graphen."
J. Combin. Th. Ser. B 16, 229-233, 1974.
(Something I read said this theorem depends on the classification of the sporadic simple groups. But since I think that was completed after 1974, perhaps the universality of this theorem became known only after the sporadic simple groups were known?)
--Dan
"Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun