Add is_cayley_graph - Githubissues

jaanos commented 8 years ago

This ticket adds a method is_cayley to GenericGraph. This method checks whether a graph or digraph (which may or may not be connected) is a Cayley graph. If requested, it also returns a permutation group, a mapping from vertices to group elements, and a generating set of the Cayley graph.

A method has_regular_subgroup has also been added to PermutationGroup_generic. It determines whether the group has a regular subgroup, and returns it if requested.

CC: @nathanncohen @dimpase

Component: graph theory

Keywords: Cayley graphs groups

Author: Janoš Vidali

Branch: c6680e7

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19586

jaanos commented 8 years ago

comment:41

Hi!

well, how about having a proper digraphs.CayleyGraph() constructor?

I'm not sure what you're trying to achieve here. The method being added here is supposed to recognize Cayley graphs, no matter how they were constructed.

That said, I think we do need a backend for GRAPE-like graphs (i.e., using an automorphism group and orbit representatives).

Janoš

dimpase commented 8 years ago

comment:42

Replying to @jaanos:

well, how about having a proper digraphs.CayleyGraph() constructor?

I'm not sure what you're trying to achieve here. The method being added here is supposed to recognize Cayley graphs, no matter how they were constructed.

a part of interface issue is that we lack (di)graphs.CayleyGraph(); if it was there it would be most natural to return such a thing on success.

That said, I think we do need a backend for GRAPE-like graphs (i.e., using an automorphism group and orbit representatives).

I have been advocating this for years, but never had time to implement it.

jaanos commented 8 years ago

comment:43

a part of interface issue is that we lack (di)graphs.CayleyGraph(); if it was there it would be most natural to return such a thing on success.

So you're saying that we should return an isomorphic graph that is marked as a Cayley graph as a certificate? Interesting, although this is probably something the user should do by themselves given the group.

Even if we don't have such a constructor, we can always relabel the vertices with group elements, and then set edge labels, just like the cayley_graph method on a group would do.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:44

Hmmmm.. True. Returning a graph whose vertices are group elements and whose edges are labelled with a group element looks cool. Plus one can even get the actual group from anyvertex.parent()...

Nathann

dimpase commented 8 years ago

comment:45

Replying to @nathanncohen:

Hmmmm.. True. Returning a graph whose vertices are group elements and whose edges are labelled with a group element looks cool. Plus one can even get the actual group from anyvertex.parent()...

vertices and edge labels ought to be words in group generators (you always need at most log_2(n) generators, at least if my memory is correct that the elementary abelian 2-groups are the worst case for the number of generators; and multiplying permutations is fast). Actually, all you need to store is "Schreier vector", and compute vertex and edge labels on the fly.

Certainly keeping edge labels for each edge is silly, as they are trivially computed from the edge labels for one fixed vertex.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:46

Yo

vertices and edge labels ought to be words in group generators

Why ? A group element does the job already.

Actually, all you need to store is "Schreier vector", and compute vertex and edge labels on the fly.

That sounds like "something you might want to have", not "something that you can request the ticket's author to implement for you, as a reviewer"

Certainly keeping edge labels for each edge is silly, as they are trivially computed from the edge labels for one fixed vertex.

Sure, but this way if you type g.edge_labels() you obtain the list of generators. It is only a proposition: I don't use cayley graph much, and though I can review some of the code the design is best chosen by those who might need the feature. You two, in the current situation.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

382c0f2 Rename transitive_subgroup to regular_subgroup

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 4aaf301 to 382c0f2

dimpase commented 8 years ago

comment:48

Replying to @nathanncohen:

Yo

vertices and edge labels ought to be words in group generators

Why ? A group element does the job already.

cause you need n^2 as opposed to n log(n) storage, making graphs that are easily handled by GRAPE out of reach.

Actually, all you need to store is "Schreier vector", and compute vertex and edge labels on the fly.

That sounds like "something you might want to have", not "something that you can request the ticket's author to implement for you, as a reviewer"

Certainly. It seems to be better to write it here than per email. I certainly not insist on it being implemented here on this ticket.

Certainly keeping edge labels for each edge is silly, as they are trivially computed from the edge labels for one fixed vertex.

Sure, but this way if you type g.edge_labels() you obtain the list of generators. It is only a proposition: I don't use cayley graph much, and though I can review some of the code the design is best chosen by those who might need the feature. You two, in the current situation.

New commits:

382c0f2 Rename transitive_subgroup to regular_subgroup

dimpase commented 8 years ago

comment:49

Replying to @dimpase:

Replying to @jaanos:

Hi!

as a switch to libgap will happen sooner or later, optimising for not reading GAP output does not seem to be that important.

I see. But should I do anything about it at this point?

this ceritainly looks better, but again, I don't like the counter-intuitive parameters of is_cayley() and weird sort of output (a pair) that you currently have. In particular the latter.

I have modelled both input and output of is_cayley after methods such as is_chordal and is_circulant.

interestingly, is_circulant implements a naive brute-force algorithm, and docs don't mention that there is a polynomial-time algorithm. (Which is also not mentioned on the wikipedia page it refers to. Perhaps I should edit the latter...)

PS. just edited the wikipedia page...

jaanos commented 8 years ago

comment:50

OK, I have just renamed the group method now, and haven't done any of the other things yet.

About a Cayley graph as a certificate: when we have an appropriate backend, sure, we should use that (or even a subclass dedicated to Cayley graphs which can compute the vertex name and edge labels on the fly). But until then we should decide what exactly to return as certificate, and that should remain so in the future.

If we want to return a Cayley graph, we could either always return a digraph (which can be nicely labelled, but won't be isomorphic to an undirected graph), or simply relabel the input graph (in case of undirected graphs we should then not use mutually inverse labels). I prefer the second option.

Janoš

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

baba4a8 Add cayley_graph_group and change the certificate to a labelled graph

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 382c0f2 to baba4a8

jaanos commented 8 years ago

comment:52

I have finally gotten around to continuing work on this ticket. So, now we've got this:

I have added a method cayley_graph_group, as suggested, which takes care of obtaining the group (or actually computing it in the case of disconnected graphs). It can be instructed not to actually return the group, but only to tell whether the graph is Cayley or not.
is_cayley calls the above method, requesting the group if a certificate is requested. The certificate is now a copy of the graph with edges labelled by members of the generating set, and vertices associated to group elements (vertex names are not changed). One may then test that the result is indeed a Cayley graph - an example is in the doctest. Of course, once we will have a separate class/backend for Cayley graphs, we can use that here.
Since set_edge_label does not work for multiedges, I have added three new parameters to copy. One is data, specifying the actual graph data to be copied (so this can be anything Graph and DiGraph accept - in this case, a list of vertices and a list of labelled edges). The other two are loops and multiedges (I don't actually use them in the final version, but I figured it might be still useful to keep them). Any of the properties of the graph not specified as a parameter are obtained from the graph itself, not from whatever data is.

So, what do you guys think?

Janoš

New commits:

baba4a8 Add cayley_graph_group and change the certificate to a labelled graph

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:53

Please remove this ugly 'data' argument in 'copy'. It will not happen.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:54

Sorry, I was rather angry. Longer answer:

I have added a method cayley_graph_group, as suggested, which takes care of obtaining the group (or actually computing it in the case of disconnected graphs). It can be instructed not to actually return the group, but only to tell whether the graph is Cayley or not.

is_cayley calls the above method, requesting the group if a certificate is requested. The certificate is now a copy of the graph with edges labelled by members of the generating set, and vertices associated to group elements (vertex names are not changed). One may then test that the result is indeed a Cayley graph - an example is in the doctest. Of course, once we will have a separate class/backend for Cayley graphs, we can use that here.

I am still against the presence of both 'is_cayley' and 'cayley_graph_group', especially if you say that the first does the job of the second already. Let us not have 300 ways to do the same thing.

In particular, I often saw often users do things like:

if self.is_cayley():
    G = self.cayley_graph_group()

Which means that they compute things twice, whenever they have both a is_* function and another one which returns the data they are actually after.

I'm beginning to think that a is_cayley_graph that would return the group if possible and False otherwise would do the job, though that's only me.

Since set_edge_label does not work for multiedges, I have added three new parameters to copy. One is data, specifying the actual graph data to be copied (so this can be anything Graph and DiGraph accept - in this case, a list of vertices and a list of labelled edges). The other two are loops and multiedges (I don't actually use them in the final version, but I figured it might be still useful to keep them). Any of the properties of the graph not specified as a parameter are obtained from the graph itself, not from whatever data is.

Keywords like 'data' caused me endless troubles in this library. It is far too unspecific, and I do not even think that you need it. From what you said it seems that you only need to perform a copy then call to_simple. Tell me if it isn't what you want.

Nathann

jaanos commented 8 years ago

comment:55

Hi!

Replying to @nathanncohen:

Sorry, I was rather angry. Longer answer:

Sorry about that, I thought you wouldn't like it. Anyway:

I am still against the presence of both 'is_cayley' and 'cayley_graph_group', especially if you say that the first does the job of the second already. Let us not have 300 ways to do the same thing.

I'm beginning to think that a is_cayley_graph that would return the group if possible and False otherwise would do the job, though that's only me.

I actually agree - I was just trying to implement what Dima had suggested. But anyway, I think it would not be wrong to let the user also have the generating set and a labelled copy of the graph if requested.

Keywords like 'data' caused me endless troubles in this library. It is far too unspecific, and I do not even think that you need it. From what you said it seems that you only need to perform a copy then call to_simple. Tell me if it isn't what you want.

I agree that having data as a parameter to copy is ugly and counter-intuitive. However, lacking a way to label the edges of a multigraph, I thought it would be easiest to just rebuild a graph with the labels, and copy already provides all copying-related stuff (an alternative would be to replicate its code).

to_simple would not work here, since I want to keep all loops and multiedges. What would be needed is a method like set_edge_labels which allows setting all labels simultaneously (including multiedges). For the purpose of this function, it would also suffice to have a parameter to set_edge_label that makes it set the same label to all parallel multiedges.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:56

Yo !!

I actually agree - I was just trying to implement what Dima had suggested. But anyway, I think it would not be wrong to let the user also have the generating set and a labelled copy of the graph if requested.

I quite like to abuse of Python's features in this respect (though I know Dima hates it), and have the same function return as much stuff as needed: G.is_cayley_graph(group=True,labelled_graph=True).

I agree that having data as a parameter to copy is ugly and counter-intuitive. However, lacking a way to label the edges of a multigraph, I thought it would be easiest to just rebuild a graph with the labels, and copy already provides all copying-related stuff (an alternative would be to replicate its code).

Is there any reason why you don't create an empty digraph and add the necessary edges? I first thought that you were trying to avoid distinguishing graph and digraph, but then I wondered what the label would be on an unlabeled edge. u/v or v/u? Seems better to always use a digraph, doesn't it?

Nathann

jaanos commented 8 years ago

comment:57

Hi!

Is there any reason why you don't create an empty digraph and add the necessary edges? I first thought that you were trying to avoid distinguishing graph and digraph, but then I wondered what the label would be on an unlabeled edge. u/v or v/u? Seems better to always use a digraph, doesn't it?

I guess this would be doable, but then other properties would also have to be set, which means duplicating the copy code. So essentially this is what the current code is doing. But then again maybe we should be happy with just copying what we really need.

As for graphs vs. digraphs, I prefer returning a graph which is actually isomorphic to the original one. Of course, the resulting digraph could always be converted to an undirected graph, but if the original graph has multiedges, this conversion would double the edges.

For the labels on undirected edges, what I currently do is pick one label and use it whenever its inverse could be used. Since vertices are associated with group elements (via set_vertices), this does not appear to be a problem.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:58

Hello,

I guess this would be doable, but then other properties would also have to be set, which means duplicating the copy code.

Don't feel forced to preserve them if you see no reason to. Most of Sage's graph methods do not do it, so it is far from being a standard. If you want to do it, however, you are quite free to do so.

As for graphs vs. digraphs, I prefer returning a graph which is actually isomorphic to the original one. Of course, the resulting digraph could always be converted to an undirected graph, but if the original graph has multiedges, this conversion would double the edges.

For the labels on undirected edges, what I currently do is pick one label and use it whenever its inverse could be used.

Sorry, I do not understand this sentence.

Since vertices are associated with group elements (via set_vertices), this does not appear to be a problem.

Nooooooo... set_vertices? You use it to store the bijection between vertices and group elements? Can't you return a dictionary instead ?

I hate those "gadget properties". They seem nice when you add them, and then you see yourself spending your nights answering idiotic questions like "what on earth should I do with set_vertices inside of mergevertices" or something like that `><`

Nathann

jaanos commented 8 years ago

comment:59

Hi!

For the labels on undirected edges, what I currently do is pick one label and use it whenever its inverse could be used.

Sorry, I do not understand this sentence.

I meant that all undirected edges (u, v) such that u*g == v or u*g^-1 == v, the same label g is used (of course, g^-1 would be just as good).

Nooooooo... set_vertices? You use it to store the bijection between vertices and group elements? Can't you return a dictionary instead ?

I hate those "gadget properties". They seem nice when you add them, and then you see yourself spending your nights answering idiotic questions like "what on earth should I do with set_vertices inside of mergevertices" or something like that `><`

Haha, it seems I hit something that shouldn't be:)

Maybe we should revert to the last commit, and just add an option to let the user have exactly what they want (group/mapping/generating set). As for the graph, I guess the best thing would be to let the user construct it themselves the way that they want.

Janoš

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8685628 Replace certificate with return_group, mapping and generators

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from baba4a8 to 8685628

jaanos commented 8 years ago

comment:61

OK, I've reverted the last commit, and instead added the parameters return_group, mapping and generators instead of certificate. I hope it's better this way:)

By the way, should the parameters all be named return_*? return_group seems to be established, while, for example, automorphism_group has a parameter orbits to specify that orbits should be returned.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:62

Hellooooooooooo,

Thank you very much for this update. Here are some comments:

Some people sometimes fight about whether 'self' should be allowed in the docstrings, .e.g: Check whether self is a Cayley graph. I don't insist on any such rule, but I usually write it on the pattern 'Check whether the graph is a Cayley graph'. As you rightfully added your method to the index, you can see that only the name of the function appears before Check whether self is a Cayley graph.. In this context, the meaning of 'self' is not clear. This being said, you will probably see it occur in some other places of Sage's code: make the change or do not make it, according to your taste. I just thought worth mentionning.
About the doctest sage: S. I am not sure that the output will be identital on all platforms: the order of the generators can change on a different architecture, and this would be reported as a broken doctest. If you have reasons to believe that it will work on all platform then it can stay, otherwise the test must be made platform-independent. This can be done by building the graph from the generators for instance. If you do not believe that it is worth checking (e.g. if it is already tested elsewhere) then you can just remove this line, or test something different.
regular_subgroup given that the default behaviour is to return a boolean, shouldn't it be named has_regular_subgroup instead?
about is_cayley returning generators: do you think that it is necessary to have this option, or should we let users call .generators() on the group object?
c, G, d, S could you give more meaningful names to those variables? I guess that 'G' is alright (even though, in a Graph function...) but d and S could easily be graph_to_group_map and generators. Or anything else you might prefer.
You do not need \ at the end of the line when a [({ is open and remains to be closed.

Can this

+                t = C[0].is_cayley(return_group=certificate)
+                if certificate:
+                    c, CG = t

be replaced by that?

+                c, CG = C[0].is_cayley(return_group=certificate)
+                if certificate:

The value None may be replaced by None uselessly, but that's not a big problem (if I don't get anything wrong)

About return tuple(out) -- there is nothing wrong with this, though I don't think it is necessary to force a 'tuple'. This is no request to change it of course, it is fine as it is if you prefer it this way.
It is better to call self.degree() than len(self.domain()).

Nathann

P.S.: Don't forget to set a ticket back to needs_review once you are done with the changes.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

Reviewer: Nathann Cohen

jaanos commented 8 years ago

comment:63

Hi!

Some quick replies:

About the doctest sage: S. I am not sure that the output will be identital on all platforms: the order of the generators can change on a different architecture, and this would be reported as a broken doctest. If you have reasons to believe that it will work on all platform then it can stay, otherwise the test must be made platform-independent. This can be done by building the graph from the generators for instance. If you do not believe that it is worth checking (e.g. if it is already tested elsewhere) then you can just remove this line, or test something different.

Yes, I was a bit worried about that. Anyway, this was intended more as a demonstration that the method works on non-simple graphs, so maybe it should be moved to the Examples section. Instead of printing out the generating set, maybe we should just print its length and the number of distinct elements, and maybe check that it contains the identity element.

about is_cayley returning generators: do you think that it is necessary to have this option, or should we let users call .generators() on the group object?

Yes, because the generating set of a Cayley graph is not the same as the set of generators of a group. A trivial example would be a complete graph - its generating set as a Cayley graph is the whole group, which can of course be generated by some subset of its elements. For a disconnected Cayley graph, on the other hand, the generating set will not even generate the whole group.

This reminds me that I should probably add a further optimization: if a (simple) graph is connected and dense (say, vertex degree more than half the order), then it may be more efficient to check for Cayleyness of its complement (in case it is disconnected it will be more efficient, otherwise the same).

Can this
+                t = C[0].is_cayley(return_group=certificate)
+                if certificate:
+                    c, CG = t
be replaced by that?
+                c, CG = C[0].is_cayley(return_group=certificate)
+                if certificate:
The value None may be replaced by None uselessly, but that's not a big problem (if I don't get anything wrong)

No, because we are not guaranteed that a tuple will be returned.

About return tuple(out) -- there is nothing wrong with this, though I don't think it is necessary to force a 'tuple'. This is no request to change it of course, it is fine as it is if you prefer it this way.

True, but other methods returning multiple data also return tuples, so I think it should stay (IMO lists should be used when the size of the output is not predetermined, and its members have the same type).

I agree with the comments that I haven't replied to. I'm a bit busy these days, so (anyone) feel free to implement these suggestions if you feel like it.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:64

Yes, I was a bit worried about that. Anyway, this was intended more as a demonstration that the method works on non-simple graphs, so maybe it should be moved to the Examples section. Instead of printing out the generating set, maybe we should just print its length and the number of distinct elements, and maybe check that it contains the identity element.

If you meant it as a 'pedagogical' doctest, then there is an easy way out: just add a '# random' flag to the doctest.

file:///home/ncohen/.Sage/src/doc/output/html/en/developer/coding_basics.html#special-markup-to-influence-tests

Yes, because the generating set of a Cayley graph is not the same as the set of generators of a group.

Arg... Sorry. Not only I am an idiot, but I already asked the same question and you gave me the very same answer >_<

This reminds me that I should probably add a further optimization: if a (simple) graph is connected and dense (say, vertex degree more than half the order), then it may be more efficient to check for Cayleyness of its complement (in case it is disconnected it will be more efficient, otherwise the same).

The .density() and .complement() method raise exceptions on non-simple graphs. I think that it is better to not care about this, unless you really need those cases and the speedup is obvious.

No, because we are not guaranteed that a tuple will be returned.

Weird. I thought you said in the doctest that a tuple will always be returned, whether the graph is a cayley graph or not, and that the additional values would be set to None if necessary.

True, but other methods returning multiple data also return tuples, so I think it should stay (IMO lists should be used when the size of the output is not predetermined, and its members have the same type).

O_o

Okay. Well. Tastes :-P

Nathann

jaanos commented 8 years ago

comment:65

Hi!

This reminds me that I should probably add a further optimization: if a (simple) graph is connected and dense (say, vertex degree more than half the order), then it may be more efficient to check for Cayleyness of its complement (in case it is disconnected it will be more efficient, otherwise the same).

The .density() and .complement() method raise exceptions on non-simple graphs. I think that it is better to not care about this, unless you really need those cases and the speedup is obvious.

That's why I said simple (and I hadn't thought out the implications of non-simple graphs). But yes, the denser the graph, the greater the probability that such a speedup will be achieved, and the greater potential of speedup in this case. In the case of multiple edges, this potential is smaller (the current method will be faster in general due to the potentially smaller automorphism group), and I agree that we should not even care about the cases when speedup is actually possible (e.g. when all multiedges appear with the same multiplicity).

No, because we are not guaranteed that a tuple will be returned.

Weird. I thought you said in the doctest that a tuple will always be returned, whether the graph is a cayley graph or not, and that the additional values would be set to None if necessary.

A tuple will be returned whenever some form of certificate is requested, regardless of whether the graph is Cayley or not. What is being differentiated here is whether the group has been requested in the first place. Although if you prefer, a call to is_cayley could be made in each branch of the if statement.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:66

Yooooooo,

A tuple will be returned whenever some form of certificate is requested, regardless of whether the graph is Cayley or not. What is being differentiated here is whether the group has been requested in the first place.

Right right, sorry.

Although if you prefer, a call to is_cayley could be made in each branch of the if statement.

The simpler the better, that's all I am looking for.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 8685628 to 95e34ee

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

95e34ee Apply Nathann's suggestions

jaanos commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-This ticket adds a method `is_cayley` to `GenericGraph`. This method checks whether a graph or digraph (which may or may not be connected) is a Cayley graph. If a certificate is requested, it also returns a permutation group and a generator set which generate this graph.
+This ticket adds a method `is_cayley` to `GenericGraph`. This method checks whether a graph or digraph (which may or may not be connected) is a Cayley graph. If requested, it also returns a permutation group, a mapping from vertices to group elements, and a generating set of the Cayley graph.

-A method `has_transitive_subgroup` has also been added to `PermutationGroup_generic`. For a given order, it determines whether the group has a subgroup of this order, and returns it if requested. If no order is given, it is taken to be the order of the group itself (i.e., the method then simply tells whether the group is transitive).
+A method `has_regular_subgroup` has also been added to `PermutationGroup_generic`. It determines whether the group has a regular subgroup, and returns it if requested.

jaanos commented 8 years ago

comment:68

Hi!

I have implemented your suggestions. Some comments:

About the doctest sage: S. I am not sure that the output will be identital on all platforms: the order of the generators can change on a different architecture, and this would be reported as a broken doctest. If you have reasons to believe that it will work on all platform then it can stay, otherwise the test must be made platform-independent. This can be done by building the graph from the generators for instance. If you do not believe that it is worth checking (e.g. if it is already tested elsewhere) then you can just remove this line, or test something different.

I've moved it to the Examples section and added a # random flag. I've also added this flag to the doctests in permgroup.py where the generators of a group are output.

regular_subgroup given that the default behaviour is to return a boolean, shouldn't it be named has_regular_subgroup instead?

Actually, the default behaviour was to return a group, but I changed it now. It seems more appropriate this way, since the method will return a regular subgroup, not the regular subgroup (if there is one in the first place). Now, the returned group (if requested) can be thought of as a certificate. Anyway, is_cayley now explicitly specifies the return_group parameter of has_regular_subgroup in both cases.

c, G, d, S could you give more meaningful names to those variables? I guess that 'G' is alright (even though, in a Graph function...) but d and S could easily be graph_to_group_map and generators. Or anything else you might prefer.

OK, I have now changed map, d and S to compute_map, map and genset, respectively.

You do not need \ at the end of the line when a [({ is open and remains to be closed.

True, but the \ in line 20891 of generic_graph.py is actually outside any parentheses.

Janoš

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:69

Hellooooooo,

True, but the \ in line 20891 of generic_graph.py is actually outside any parentheses.

Sigh... Right. You write extremely clean code, y'know?

I re-read everything and added a couple of 'default values' for the arguments in the INPUT section, in a commit at public/19586. You can change the branch's name on this ticket if you agree with it.

Dima? Could you please review the code of _regular_subgroup_gap? I reviewed everything else but I'm not knowledgeable for that.

If this part is good for you, then this ticket can be changed to positive_review.

THaaaaaaaaaaaaanks,

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 95e34ee to a58a734

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`34f9212`	`Check for Cayleyness of the complement if the graph is simple with density > 1/2`
`d5b8bc7`	`trac #19586: Merged with 7.0`
`278bb47`	`trac #19586: Review`
`a58a734`	`Merge branch 'public/19586' into is_cayley_graph-gap`

jaanos commented 8 years ago

comment:71

Hi!

True, but the \ in line 20891 of generic_graph.py is actually outside any parentheses.

Sigh... Right. You write extremely clean code, y'know?

Thanks :)

I re-read everything and added a couple of 'default values' for the arguments in the INPUT section, in a commit at public/19586. You can change the branch's name on this ticket if you agree with it.

Thank you - I've also added the optimization for dense simple graphs that I was talking about.

Janoš

dimpase commented 8 years ago

comment:72

I probably don't understand something, but why is the existence of a regular subgroup sufficient for the graph to be Cayley? Indeed, one seem to need in addition that this subgroup is generated by the elements corresponding to the neighbours of a vertex.

E.g. I can construct a cubic, arc-transitive, digraph on 16 vertices, with a regular subgroup being elementary abelian, i.e. in particular having 4 generators. The underlying graph has degree 6, so it is OK as a Cayley graph, but not OK as a Cayley digraph, as 3 generators (the out-degree of the digraph) are not enough!

New commits:

`34f9212`	`Check for Cayleyness of the complement if the graph is simple with density > 1/2`
`d5b8bc7`	`trac #19586: Merged with 7.0`
`278bb47`	`trac #19586: Review`
`a58a734`	`Merge branch 'public/19586' into is_cayley_graph-gap`

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:73

Hmmmmmmm :-/

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:74

It's true that almost everybody seems to suppose that a cayley graph is connected.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:75

Should this raise an exception, by the way? :-/

sage: groups.permutation.Dihedral(4).cayley_graph(generators=[(1,2,3,4)]).show()

Nathann

dimpase commented 8 years ago

comment:76

Replying to @nathanncohen:

It's true that almost everybody seems to suppose that a cayley graph is connected.

I think I can construct a connected cubic arc-transitive digraph on 2¹⁰ vertices, and thus a connected vertex-transitive graph of degree 6, that has a regular subgroup of automorphisms that is elementary abelian, i.e. needs 10 generators to be generated. Thus this graph won't be a Cayley for this subgroup. But this code would happily say that the graph is Cayley...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:77

I don't get it: if what you say were true, it would mean that the action of that regular subgroup upon the edges incident to a fixed vertex would yield a disconnected 6-regular graph.

On the other hand, this 6-regular disconnected graph is a subgraph of the connected 6-regular graph you started from, so ... no?

Nathann

jaanos commented 8 years ago

comment:78

Hi!

Let's see... if the automorphism group has a regular subgroup G, then we can pick any vertex w and construct a bijective mapping that maps a group element g to the vertex g^w. Now, suppose we have an arc uv such that group elements g and h map to u and v, respectively. Then we may label the arc by e = g^-1 h, and any automorphism a from G will map uv = g^w h^w to (ag)^w (ah)^w, i.e. an arc with the same label. Since such a graph is necessarily vertex-transitive, it follows that the (multi)set of labels on arcs starting in a vertex is independent of the choice of said vertex. The Cayley graph of G with said (multi)set as its generating set is then isomorphic to our graph.

Do you find any flaw in the above argument? Also, can you provide the graphs which you claim to be counterexamples?

Janoš

dimpase commented 8 years ago

comment:79

Replying to @nathanncohen:

I don't get it: if what you say were true, it would mean that the action of that regular subgroup upon the edges incident to a fixed vertex would yield a disconnected 6-regular graph.

no, it would not, it would give the whole graph. But the subgroup will not be generated by the neighbours of the identity in the graph. Indeed, the minimal degree of a Cayley graph of this group is 10 (as one needs at least 10 generators). Thus this graph is not a Cayley graph of this group.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:80

no, it would not, it would give the whole graph.

Arg. We miss each other: I use a different observation: because you tell me that your group cannot be generated by <10 elements, then surely when your compute the orbit of those edges there cannot be a path from every vertex to every other. Because otherwise, well, your 6 vertices would be sufficient to generate the subgroup.

So it is both disconnected (by this observation) and connected (by yours) and so it is impossible?...

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:81

Do you find any flaw in the above argument? Also, can you provide the graphs which you claim to be counterexamples?

I agree with you everywhere short of one thing: if the graph you started with is not connected, then the set you are talking about is not a generating set, e.g. : take the disjoint union of two cliques of size n, and as a regular subgroup take two disjoint cycles of order n plus a reflections that exchanges both.

Nathann

jaanos commented 8 years ago

comment:82

Replying to @nathanncohen:

Do you find any flaw in the above argument? Also, can you provide the graphs which you claim to be counterexamples?

I agree with you everywhere short of one thing: if the graph you started with is not connected, then the set you are talking about is not a generating set, e.g. : take the disjoint union of two cliques of size n, and as a regular subgroup take two disjoint cycles of order n plus a reflections that exchanges both.

In this case the set does not generate the group, but it still is a generating set in the sense that it generates the graph. In any case, disconnected graphs are given a special treatment, checking Cayleyness only for a connected component.

Now, whether we allow Cayley graphs to be disconnected is just a matter of definition. I know that usually they are assumed to be connected, but in my opinion we should allow disconnected graphs to be called Cayley (it even allows this method to make optimizations by looking at complements). So the example you gave above is fine without raising an exception IMO.

Janoš

dimpase commented 8 years ago

comment:83

Replying to @jaanos:

Let's see... if the automorphism group has a regular subgroup G, then we can pick any vertex w and construct a bijective mapping that maps a group element g to the vertex g^w. Now, suppose we have an arc uv such that group elements g and h map to u and v, respectively. Then we may label the arc by e = g^-1 h, and any automorphism a from G will map uv = g^w h^w to (ag)^w (ah)^w, i.e. an arc with the same label. Since such a graph is necessarily vertex-transitive, it follows that the (multi)set of labels on arcs starting in a vertex is independent of the choice of said vertex. The Cayley graph of G with said (multi)set as its generating set is then isomorphic to our graph.

Do you find any flaw in the above argument?

it is certainly true that you can assume w=1. So you have the neighbours of 1 in the graph (with its vertices labelled by the elements of G) say g₁,...,g_k. Now you need an argument that g₁,...,g_k generate G. I don't see it in what you wrote above.

Also, can you provide the graphs which you claim to be counterexamples?

I'll try. (Or show me that they don't exist...)

sagemath / sage

Add is_cayley_graph #19586