#16370 closed enhancement (fixed)
OA(k,n) strongly regular graphs
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | graph theory | Keywords: | |
Cc: | vdelecroix, knsam, dimpase, brett | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 44c01db (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | #16388 | Stopgaps: |
Description (last modified by )
Turns out that orthogonal arrays give strongly regular graphs. Isn't that cool ?
Brouwer's website is filled with references to "OA" :-)
- http://www.win.tue.nl/~aeb/graphs/srg/srgtab251-300.html
- http://www.win.tue.nl/~aeb/graphs/OA.html
Nathann
Change History (51)
comment:1 Changed 7 years ago by
- Branch set to u/ncohen/16370
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Commit set to b35cb70af5ae6c47669d5d19a9602ff7a5267005
comment:3 Changed 7 years ago by
please change Professor Brouwer
to Andries Brouwer
. Andries is against these sorts of formalities (I know him for, like 25 years).
comment:4 Changed 7 years ago by
- Commit changed from b35cb70af5ae6c47669d5d19a9602ff7a5267005 to d71f32cbcf327d97e4047984ae3499e0dedcae0f
Branch pushed to git repo; I updated commit sha1. New commits:
d71f32c | trac #16370: Reviewer's comment
|
comment:5 Changed 7 years ago by
Done.
Nathann
comment:6 Changed 7 years ago by
- Status changed from needs_review to needs_work
Error building the documentation. Traceback (most recent call last): File "/home/ralf/sage/src/doc/common/builder.py", line 1477, in <module> getattr(get_builder(name), type)() File "/home/ralf/sage/src/doc/common/builder.py", line 276, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/home/ralf/sage/src/doc/common/builder.py", line 487, in _wrapper x.get(99999) File "/home/ralf/sage/local/lib/python/multiprocessing/pool.py", line 554, in get raise self._value OSError: [graphs ] /home/ralf/sage/src/doc/en/reference/graphs/sage/graphs/graph_generators.rst:6: WARNING: Duplicate explicit target name: "andries brouwer's website". make: *** [doc-html] Error 1
comment:7 Changed 7 years ago by
- Commit changed from d71f32cbcf327d97e4047984ae3499e0dedcae0f to 57d979f22bd56536648945c3821ccf872fcfbeb9
Branch pushed to git repo; I updated commit sha1. New commits:
57d979f | trac #16370: Broken doc
|
comment:9 Changed 7 years ago by
- Commit changed from 57d979f22bd56536648945c3821ccf872fcfbeb9 to 90a72bd39d74c24cb548e5b7dc5995c67ac386f8
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
90a72bd | trac #16370: OA(k,n) strongly regular graphs
|
comment:10 follow-up: ↓ 11 Changed 7 years ago by
- Status changed from needs_review to needs_work
Hi Nathann,
Could you write in the docs:
- how the graph is built
- what are the parameters (v=n2, k=k(n-1), lambda=(k-1)(k-2)+n-2, mu=k(k-1))
Might also be good in the doctests, i.e.
sage: OA = designs.WHATEVER_OA(3,7) sage: G = graphs.OrthogonalArrayGraph(OA) sage: G.vertices() ... sage: G.is_strongly_regular(parameters=True) (49, 18, 7, 6) sage: 7^2, 3*(7-1), (3-1)*(3-2)+7-2, 3*(3-1) (49, 18, 7, 6)
The graph depends on the OA(k,n), doesn't it? It might really be that we already have for some parameters several constructions of OA... and hence as many OA-graphs. Would it be possible to have more open input, like def OrthogonalArrayGraph(data, n=None)
returning what you did if data=k
and n=n
but also returns what we think if data
is set to an OA
?
The construction is actually much more general: from any set of subsets we can build such a graph. Wikipedia calls it an Intersection graph (note: any graph can be obtained that way). When the set of subsets is a transversal design the obtained graph has nice properties but I am quite sure that implementing graphs.IntersectionGraph
would make more sense.
Vincent
comment:11 in reply to: ↑ 10 Changed 7 years ago by
Y666666666666 !!
Could you write in the docs:
- how the graph is built
Isn't that written already ?..
The intersection graph of the block of a `TD(k,n)` (see + :func:`~sage.combinat.designs.orthogonal_arrays.orthogonal_array`) is a + strongly regular graph.
That's a definition of the graph.
- what are the parameters (v=n2, k=k(n-1), lambda=(k-1)(k-2)+n-2, mu=k(k-1))
The parameters associated with a strongly regular graph.
sage: Graph.is_strongly_regular??
Might also be good in the doctests, i.e.
sage: OA = designs.WHATEVER_OA(3,7) sage: G = graphs.OrthogonalArrayGraph(OA) sage: G.vertices() ... sage: G.is_strongly_regular(parameters=True) (49, 18, 7, 6) sage: 7^2, 3*(7-1), (3-1)*(3-2)+7-2, 3*(3-1) (49, 18, 7, 6)
I don't get what you want me to add.... Only a call to G.vertices()
? Brouwer gives the actual parameters of the final OA graph but I don't do this in the docstring, so well....
The graph depends on the OA(k,n), doesn't it?
Yes.
It might really be that we already have for some parameters several constructions of OA... and hence as many OA-graphs. Would it be possible to have more open input, like
def OrthogonalArrayGraph(data, n=None)
returning what you did ifdata=k
andn=n
but also returns what we think ifdata
is set to anOA
?
We could have a graph constructos graphs.IntersectionGraph
taking as an argument a list of sets and returning the corresponding graph. Would make more sense than a dedicated version for OA.
The construction is actually much more general: from any set of subsets we can build such a graph. Wikipedia calls it an Intersection graph (note: any graph can be obtained that way). When the set of subsets is a transversal design the obtained graph has nice properties but I am quite sure that implementing
graphs.IntersectionGraph
would make more sense.
Ahem. I should read the email before I answer them. Indeed, indeed :-P
Nathann
comment:12 Changed 7 years ago by
- Status changed from needs_work to needs_review
comment:13 follow-up: ↓ 14 Changed 7 years ago by
So, you guys decided against implementing a generic graphs.IntersectionGraph
constructor?
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 7 years ago by
Replying to knsam:
So, you guys decided against implementing a generic
graphs.IntersectionGraph
constructor?
I did not decide anything. I asked questions to Nathann and he puts the ticket back in needs review... which might mean that I have to question his answers to my questions...
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 7 years ago by
So, you guys decided against implementing a generic
graphs.IntersectionGraph
constructor?I did not decide anything. I asked questions to Nathann and he puts the ticket back in needs review... which might mean that I have to question his answers to my questions...
Yep yep... Actually creating this constructor can be useful... Right now you can build such graphs easily but nobody knows the syntax :
sage: random_sets = [Subsets(range(15)).random_element() for _ in range(15)] sage: g = Graph([random_sets,lambda x,y : x&y])
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 17 Changed 7 years ago by
Replying to ncohen:
So, you guys decided against implementing a generic
graphs.IntersectionGraph
constructor?I did not decide anything. I asked questions to Nathann and he puts the ticket back in needs review... which might mean that I have to question his answers to my questions...
Yep yep... Actually creating this constructor can be useful... Right now you can build such graphs easily but nobody knows the syntax :
sage: random_sets = [Subsets(range(15)).random_element() for _ in range(15)] sage: g = Graph([random_sets,lambda x,y : x&y])
Hi,
So, what is the point of the ticket if we can already do
sage: g = Graph([map(Set, designs.transversal_design(3,7)), lambda x,y : x&y])
Moreover, the graph you obtain is also strongly regular with BIBD input
sage: BIBD = designs.BalancedIncompleteBlockDesign(31,6) sage: V = map(Set, BIBD.blocks()) sage: G = Graph([V, lambda x,y: x&y]) sage: G.is_strongly_regular(parameters=True) (31, 32, 31, -1)
I would rather add those examples to the documentation (of both designs and graphs). We could possibly add them to the documentation of the not yet existing graphs.IntersectionGraph
.
Vincent
comment:17 in reply to: ↑ 16 ; follow-ups: ↓ 18 ↓ 19 Changed 7 years ago by
Yo !
So, what is the point of the ticket if we can already do
sage: g = Graph([map(Set, designs.transversal_design(3,7)), lambda x,y : x&y])
Several points :
1) To say that these graphs are stronly regular, and to give them a name such that a guy looking at Brouwer's table can build them here
2) The implementation is better : the syntax above checks whether any two sets have a non-empty intersection, which is not what this code does
3) It may later be useful to have a large collection of constructors for "interesting" graphs (and strongly regular graphs ARE interesting) to check conjectures and stuff
4) We both agree that we needs a graphs.IntersectionGraph
function because the syntax above is not very natural, don't tell me now that user should find it by themselves :-P
Moreover, the graph you obtain is also strongly regular with BIBD input
sage: BIBD = designs.BalancedIncompleteBlockDesign(31,6) sage: V = map(Set, BIBD.blocks()) sage: G = Graph([V, lambda x,y: x&y]) sage: G.is_strongly_regular(parameters=True) (31, 32, 31, -1)
Err... Well, this is actually a bug report. The parameters must always be positive. Will look at it right now.
I would rather add those examples to the documentation (of both designs and graphs). We could possibly add them to the documentation of the not yet existing
graphs.IntersectionGraph
.
Tell me if my answers above convinced you.
Nathann
comment:18 in reply to: ↑ 17 Changed 7 years ago by
Err... Well, this is actually a bug report. The parameters must always be positive. Will look at it right now.
This is now #16433. By the way your BIBD is a projective plane, thus all blocks intersect, thus the intersection graph is a clique, and a clique is not strongly regular for a stupid reason that I do not like.
It is an exception in the definition.
A stupid one.
Anyway.
Nathann
comment:19 in reply to: ↑ 17 ; follow-up: ↓ 22 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_work
Replying to ncohen:
[...]
Tell me if my answers above convinced you.
Yes: this ticket should not go without a graphs.IntersectionGraph
. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc of graphs.IntersectionGraph
.
For the parameters: they are explicit in terms of (k,n) for TD and (v,k) for BIBD.
- for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
- for BIBD(v,k): lambda=(k-1)2+(v-1)/(k-1)-2, mu=k2
and this should be mentioned and tested.
By the way, why is there no BIBD in the Brouwer table?
Vincent
comment:20 follow-up: ↓ 24 Changed 7 years ago by
Hi there,
For BIBD(v,k,1) there is another standard terminology which is Steiner 2-designs S(2,k,v). So if we care about the Brouwer table then we would also add a graphs.SteinerDesignGraph
instead of a BIBD one. More generally all Steiner systems give strongly regular graphs.
and even more generally, it is written that the block graph of a quasi-symmetric design is strongly regular.
Vincent
comment:21 follow-up: ↓ 25 Changed 7 years ago by
I think it would be misleading to call it a Steiner design graph, as an incidence system can give rise to a graph in atleast three different ways:
- Levi Graph: this is a bipartite graph whose vertices are points and lines in the system and adjacency is the incidence of the incidence system.
- Adjacency graph: the points are the vertices; two vertices are adjacent if they are incident in a common line.
- Block Intersection graph: the vertices are lines of the system and two vertices are adjacent if they meet in some fixed condition on the number of points.
As I indicated above, it is common to call the graphs that we are talking about as Block intersection graphs.
A quasi-symmetric design is a 2-design with atmost two block intersection numbers. Those q.s designs with only one block intersection number are the square (or symmetric) 2-designs. One can solve the equations one obtains by using Fischer's variance counting to get the parameters of the SRG in this case.
Curiously, petersen graph is the block intersection graph of the 2-design 2-(6, 3, 2) (this is a quasi-symmetric design: any two blocks meet in 0 points or 1 point) where you define adjacency among blocks as "being disjoint". See here.
Hope this is helpful.
comment:22 in reply to: ↑ 19 Changed 7 years ago by
Yo !
Yes: this ticket should not go without a
graphs.IntersectionGraph
. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc ofgraphs.IntersectionGraph
.
Intersection graphs are something we should add, but it is not a dependency of this ticket so it will be done elsewhere.
- for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
I added a line about that in the construction of the orthogonal array graph, see commits.
By the way, why is there no BIBD in the Brouwer table?
This has been solved, Vincent sent an email to Brouwer.
Nathann
comment:23 Changed 7 years ago by
- Commit changed from 90a72bd39d74c24cb548e5b7dc5995c67ac386f8 to e3c1c2180178c94d883db945dc33f2b457330cbc
comment:24 in reply to: ↑ 20 Changed 7 years ago by
Yo !
For BIBD(v,k,1) there is another standard terminology which is Steiner 2-designs S(2,k,v). So if we care about the Brouwer table then we would also add a
graphs.SteinerDesignGraph
instead of a BIBD one. More generally all Steiner systems give strongly regular graphs.
As you saw I asked him to confirm that not all graphs of Steiner Systems with t>2 were strongly regular graphs, as I see no reason why this shold be true.
Which is also why I do not like "SteinerDesignGraph?" but at the very least "Steiner2DesignGraph", even though it "contradicts the terminology" we already use, i.e. BIBD.
Nathann
comment:25 in reply to: ↑ 21 Changed 7 years ago by
Yo !
I think it would be misleading to call it a Steiner design graph, as an incidence system can give rise to a graph in atleast three different ways:
HMmmm.... Well, my aim here was to implement a new class of strongly regular graphs that appears on Brouwer's website. The constructions you mention are interesting too but to me they really belong to the "design" world while those here belong to the "graph theory world", even though the meaning of this is a bit vague :-P
In my head it is more as if anybody who would want to build those other graphs would go toward designs first, while in the latter case they would go toward graphs OR designs.
Thus, we need a constructor for these particular strongly regular graphs. AND we will need to add a BlockDesign?.intersection_graph someday along with the others
Hope this is helpful.
Yep yep. It was a discussion about user interface almost from the beginning.
Nathann
comment:26 Changed 7 years ago by
- Status changed from needs_work to needs_review
As I believe I answered all questions... O_o
Nathann
comment:27 follow-up: ↓ 28 Changed 7 years ago by
Replying to ncohen:
Yo !
Yes: this ticket should not go without a
graphs.IntersectionGraph
. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc ofgraphs.IntersectionGraph
.Intersection graphs are something we should add, but it is not a dependency of this ticket so it will be done elsewhere.
All right. But as Brouwer said himself in his answer it would be much more consistent to have
sage: designs.MyPreferedDesign(x,y,z).block_intersection_graph()
and not
sage: graphs.BlockIntersectionGraphFromMyPreferedDesign(x,y,z)
- for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
I added a line about that in the construction of the orthogonal array graph, see commits.
hum: k=k(n-1)
I see two more obstructions right now:
- having a function with two integers as input makes anybody think that there is a unique graph associated with all OA(k,n). I do not believe that this is True. It must be very clear in the documentation.
- the function
designs.orthogonal_array
might not give the same output between two releases of Sage. So if somebody starts working on OA(5,19) and loves it and find out that three months after her graph disappear, it would be a disaster.
Vincent
comment:28 in reply to: ↑ 27 Changed 7 years ago by
Yo !
All right. But as Brouwer said himself in his answer it would be much more consistent to have
sage: designs.MyPreferedDesign(x,y,z).block_intersection_graph()
I would be interested to see the line of his email that mention either a class or a method, but this is a good syntax anyway, and you will find the same in my comment above.
and not
sage: graphs.BlockIntersectionGraphFromMyPreferedDesign(x,y,z)
Well then I am sorry for him, but I study graph theory and I know I wanted to build strongly regular graphs before knowing what an OA is. And I believe that it makes sense to have as many constructors of strongly regular graphs in graph.*
, even though the graphs could be built by other means. That's more or less the point of having a database of graph constructors, same for groups, same for words, same for everything else. Don't you have both a words.ThueMorseWord
and words.FixedPointOfMorphism
?
hum: k=k(n-1)
Ahah. Yeah, I know. I tried to phrase it to avoid confusions, but .... yeah :-P
If you see another way..
I see two more obstructions right now:
- having a function with two integers as input makes anybody think that there is a unique graph associated with all OA(k,n). I do not believe that this is True. It must be very clear in the documentation.
No problem. I can even add that it may change between versions of Sage.
- the function
designs.orthogonal_array
might not give the same output between two releases of Sage. So if somebody starts working on OA(5,19) and loves it and find out that three months after her graph disappear, it would be a disaster.
A disaster indeed. I will mention that too in a second.
Nathann
comment:29 Changed 7 years ago by
Here it is. We will also have to add a similar warning in the OA module someday (about results changing/disappearing). Though given that the goal is to match the results of the MOLS I do not think we should worry too much about designs disappearing, it will be the other way around :-P
Really, the heuristic to find holes can only give better results than those which are expected in theory, as we deal with actual designs and do not consider the "general properties of some OA(k,n)". We know more about a single design that theory does, and we can compute maximum independent sets while they can't.
And if some construction requires a specific OA, well, they will have to explain it somewhere an we can then implement it.
Branch updated !
Nathann
comment:30 Changed 7 years ago by
- Commit changed from e3c1c2180178c94d883db945dc33f2b457330cbc to e469bb5b23d7862b48082f1cba9fd946dd7dc406
Branch pushed to git repo; I updated commit sha1. New commits:
e469bb5 | trac #16370: Warnings in the constructor
|
comment:31 follow-ups: ↓ 32 ↓ 33 Changed 7 years ago by
Hi,
An OA does not determine uniquely a graph. As Kanappan said there are at least three natural ones and there are many more non-trivial constructions. So calling it graphs.OrthogonalArrayGraph
completely misleading.
About the syntax, let me cite Andries Brouwer:
If you have a set with a collection of subsets, that is called a hypergraph, and the subsets are called hyperedges. Given a hypergraph, one can make the intersection graph. The vertices of the hypergraph are the hyperedges. Two distinct vertices are adjacent when their intersection is nonempty. This is a construction that occurs in many different places. A design is a hypergraph with certain regularity properties. But this intersection graph is needed for many types of design.
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
So the name could be either graphs.IntersectionGraphOfOneOrthogonalArray
or simply a subcase of graphs.IntersectionGraph
. And I am in favour of the second one.
Vincent
comment:32 in reply to: ↑ 31 Changed 7 years ago by
An OA does not determine uniquely a graph. As Kanappan said there are at least three natural ones and there are many more non-trivial constructions. So calling it
graphs.OrthogonalArrayGraph
completely misleading.
WTF MAN ! THIS IS THE TERMINOLOGY USED ON ALL PAGES OF BROUWER'S WEBSITE ! I am not the one who made this terminology, go tell him !
About the syntax, let me cite Andries Brouwer:
Be honest and also copy/paste the answer I gave him.
If you have a set with a collection of subsets, that is called a hypergraph, and the subsets are called hyperedges. Given a hypergraph, one can make the intersection graph. The vertices of the hypergraph are the hyperedges. Two distinct vertices are adjacent when their intersection is nonempty. This is a construction that occurs in many different places. A design is a hypergraph with certain regularity properties. But this intersection graph is needed for many types of design.
I know what an intersection graph is and I said ONE THOUSAND FUCKING TIMES that we need a contructor for that. That's totally unrelated.
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
Copy/paste my answer to that. Or create a ticket to remove the words from words.*
which can be obtained through words.FixedPointOfMorphism
.
THIS DOES NOT MAKE ANY F* SENSE !
So the name could be either
graphs.IntersectionGraphOfOneOrthogonalArray
or simply a subcase ofgraphs.IntersectionGraph
. And I am in favour of the second one.
I don't give a fuck. Either you think a bit or we close this ticket as wontfix, I am tired of discussing trivialities forever. I have work to do.
Nathann
comment:33 in reply to: ↑ 31 Changed 7 years ago by
Okay, as you quoted his email but did not quote what I answered to him I paste it here.
If you have a set with a collection of subsets, that is called a hypergraph, and the subsets are called hyperedges. Given a hypergraph, one can make the intersection graph. The vertices of the hypergraph are the hyperedges. Two distinct vertices are adjacent when their intersection is nonempty. This is a construction that occurs in many different places. A design is a hypergraph with certain regularity properties. But this intersection graph is needed for many types of design.
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
It does.
All graphs are intersection graphs, and yet we have different functions to create graphs.
Petersen's graph is a Kneser Graph, yet we have both a graphs.PetersenGraph
and a graphs.KneserGraph
function.
There are different ways to create several graphs, and sometimes the planar embeddings associated with them changes depending on which function you call. Besides, if we have a function for BIBD or a function for OA graphs we can add information there about their parameters about strongl regular graphs, and it would have no meaning to add this in a much more general function handling intersection graph.
Besides, some people who read your web page and who may want to create the strongly regular graphs you mention may have absolutely no interest in knowing how they are built, and they may not know even what a design is. I am not just talking, a colleague of mine who could not care less about designs wanted me to implement the graphs of some generalized quadrangle just the other day as well as other things, and she it typically of this type : she wants to work on the graph, but she is not sufficiently interested in the subject to try to learn what an OA is and how they can be built.
Besides, we may want n the future to build an internal database of strongly regular graphs in Sage, and it is interesting for us to know that the functions only have to be fed with integers and not wit something more complicated like OA that we should take from somewhere else. It is better if all functions expect the same kind of arguments.
Nathann
comment:34 Changed 7 years ago by
Okay man.... I really need this ticket to make it in, because I have a lot of useful work above and I don't want to give all this up because of terminology problems.
I also need a function which returns this OA(k,n) graph, not only because it is interesting for guys studying graph theory who may want to have more strongly regular graphs, but also because it is useful in the constructions.
The theorems I implement these days all begin with "If there exists a TD(...), a TD(...), a TD(...) then there exists a TD(...)", and so it appears to me that I need a function which returns "a TD(...)" even though it may not be unique.
What can I do to get this in ?
Nathann
comment:35 follow-up: ↓ 36 Changed 7 years ago by
Hi Nathann,
As OrthogonalArrayGraph
is ambiguous, what do you think of OrthogonalArrayIntersectionGraph
or OrthogonalArrayBlockGraph
or OrthogonalArrayBlockIntersectionGraph
?
At least, allow the function to be fed with an OA as I suggested in comment:10.
def OrthogonalArrayGraph(data, n=None): if n is not None: data = int(data) OA = designs.orthogonal_array(data,n) else: assert is_orthogonal_array(data) OA = data ...
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
Vincent
comment:36 in reply to: ↑ 35 ; follow-up: ↓ 38 Changed 7 years ago by
Yo !
As
OrthogonalArrayGraph
is ambiguous, what do you think ofOrthogonalArrayIntersectionGraph
orOrthogonalArrayBlockGraph
orOrthogonalArrayBlockIntersectionGraph
?
This graph is not the intersection graph of the blocks of an OA. If you insist, I prefer designs.OrthogonalArrayBlockGraph
, because to me 'block' has absolutely no meaning in this context.
At least, allow the function to be fed with an OA as I suggested in comment:10.
Ok. Note that this makes sense only because the graph is NOT the intersection graph of the blocks of an OA (which are not even sets but rows with non necessarily distinct coordinates), and that as a result the future syntax graphs.IntersectionGraph(designs.orthogonal_array(k,n))
would not give the same result.
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
I can relabel an OA. The graphs will be isomorphic but different.
Nathann
comment:37 Changed 7 years ago by
Let me add that I don't see how "graphs.OrthogonalArrayGraph
" is more ambiguous than "graphs.OrthogonalArrayBlockGraph
", but at least it is not plainly wrong like the other names.
comment:38 in reply to: ↑ 36 ; follow-up: ↓ 39 Changed 7 years ago by
Replying to ncohen:
Yo !
As
OrthogonalArrayGraph
is ambiguous, what do you think ofOrthogonalArrayIntersectionGraph
orOrthogonalArrayBlockGraph
orOrthogonalArrayBlockIntersectionGraph
?This graph is not the intersection graph of the blocks of an OA. If you insist, I prefer
graphs.OrthogonalArrayBlockGraph
, because to me 'block' has absolutely no meaning in this context.
You meant intersection
has no meaning ? It depends on how you see the blocks. If you consider them as subsets of {0,...,n-1}k then it is the intersection graph of the blocks.
At least, allow the function to be fed with an OA as I suggested in comment:10.
Ok. Note that this makes sense only because the graph is NOT the intersection graph of the blocks of an OA (which are not even sets but rows with non necessarily distinct coordinates), and that as a result the future syntax
graphs.IntersectionGraph(designs.orthogonal_array(k,n))
would not give the same result.
Right.
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
I can relabel an OA. The graphs will be isomorphic but different.
Of course, I meant non-isomorphic.
comment:39 in reply to: ↑ 38 ; follow-up: ↓ 41 Changed 7 years ago by
You meant
intersection
has no meaning ? It depends on how you see the blocks.
Nono. I meant that for me "Block" has no meaning there. "intersection" on the other hand is just wrong. This graph is the intersection graph of a TD, not the intersection graph of an OA whose rows are not even sets.
If you consider them as subsets of {0,...,n-1}k then it is the intersection graph of the blocks.
I would be delighted to hear how you define such an operation, but let's get this done first.
I can relabel an OA. The graphs will be isomorphic but different.
Of course, I meant non-isomorphic.
I just finished the job for "different OA". If you want non-isomorphic OA provide them.
Nathann
comment:40 Changed 7 years ago by
- Commit changed from e469bb5b23d7862b48082f1cba9fd946dd7dc406 to 7b73bc55865f7c7bd454dd047dc38f0ed2ff58be
comment:41 in reply to: ↑ 39 Changed 7 years ago by
Replying to ncohen:
You meant
intersection
has no meaning ? It depends on how you see the blocks.Nono. I meant that for me "Block" has no meaning there. "intersection" on the other hand is just wrong. This graph is the intersection graph of a TD, not the intersection graph of an OA whose rows are not even sets.
If you consider them as subsets of {0,...,n-1}k then it is the intersection graph of the blocks.
I would be delighted to hear how you define such an operation, but let's get this done first.
Sorry, I should have said "disjoint union" instead of "product".
I can relabel an OA. The graphs will be isomorphic but different.
Of course, I meant non-isomorphic.
I just finished the job for "different OA". If you want non-isomorphic OA provide them.
Let me work for a minute.
comment:42 Changed 7 years ago by
- Status changed from needs_review to needs_work
Examples with OA(3,4)
sage: oa0 = [[0, 0, 1], [0, 1, 3], [0, 2, 0], [0, 3, 2], ....: [1, 0, 3], [1, 1, 1], [1, 2, 2], [1, 3, 0], ....: [2, 0, 0], [2, 1, 2], [2, 2, 1], [2, 3, 3], ....: [3, 0, 2], [3, 1, 0], [3, 2, 3], [3, 3, 1]] sage: oa1 = [[0, 0, 2], [0, 1, 0], [0, 2, 3], [0, 3, 1], ....: [1, 0, 3], [1, 1, 1], [1, 2, 0], [1, 3, 2], ....: [2, 0, 0], [2, 1, 2], [2, 2, 1], [2, 3, 3], ....: [3, 0, 1], [3, 1, 3], [3, 2, 2], [3, 3, 0]] sage: g0 = graphs.OrthogonalArrayBlockGraph(3,4,oa0) sage: g1 = graphs.OrthogonalArrayBlockGraph(3,4,oa1) sage: g0.is_isomorphic(g1) False
And actually they are quite different
sage: g0.automorphism_group().order() 1152 sage: g1.automorphism_group().order() 192
comment:43 Changed 7 years ago by
- Status changed from needs_work to needs_review
It would have been kind to write the commit yourself.
Anyway, here it is.
Nathann
comment:44 Changed 7 years ago by
- Commit changed from 7b73bc55865f7c7bd454dd047dc38f0ed2ff58be to d1e272f81fbd464af0f46199faa3b3fb1eda2376
Branch pushed to git repo; I updated commit sha1. New commits:
d1e272f | trac #16370: Reviewer's comments 2
|
comment:45 Changed 7 years ago by
Hi,
Two non-isomorphic OA(k,n) might give isomorphic intersection graph (exercise ;-P). I modified the documentation accordingly.
I put a k'
for the parameters of the srg to avoid ambiguity with the k
of the TD.
I exchanged the 1 and 2 in the last column of oa1
, that way it looks closer to oa0
.
The graph g0
is actually an affine polar graph, I added it to the documentation. I tried other constructions mentioned in the Brouwer table to find g1
but I did not succeed.
Have a look at u/vdelecroix/16370. Tests pass and documentation build so set to positive review after my commit if you like it.
Vincent
comment:46 Changed 7 years ago by
- Branch changed from u/ncohen/16370 to u/vdelecroix/16370
- Commit changed from d1e272f81fbd464af0f46199faa3b3fb1eda2376 to bdae80af1b51e30d9bd823a8c9aba7af41325d3d
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to positive_review
New commits:
bdae80a | trac #16370: more docs
|
comment:47 follow-up: ↓ 48 Changed 7 years ago by
- Status changed from positive_review to needs_work
sage -t --long src/sage/graphs/generators/intersection.py ********************************************************************** File "src/sage/graphs/generators/intersection.py", line 464, in sage.graphs.generators.intersection.OrthogonalArrayBlockGraph Failed example: G = graphs.OrthogonalArrayBlockGraph(4,6) Expected: Traceback (most recent call last): ... NotImplementedError: I don't know how to build this orthogonal array! Got: <BLANKLINE> Traceback (most recent call last): File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute exec compiled in globs File "<doctest sage.graphs.generators.intersection.OrthogonalArrayBlockGraph[20]>", line 1, in <module> G = graphs.OrthogonalArrayBlockGraph(Integer(4),Integer(6)) File "/home/release/Sage/local/lib/python2.7/site-packages/sage/graphs/generators/intersection.py", line 480, in OrthogonalArrayBlockGraph OA = orthogonal_array(k,n) File "/home/release/Sage/local/lib/python2.7/site-packages/sage/combinat/designs/orthogonal_arrays.py", line 857, in orthogonal_array raise NotImplementedError("I don't know how to build an OA({},{})!".format(k,n)) NotImplementedError: I don't know how to build an OA(4,6)!
comment:48 in reply to: ↑ 47 Changed 7 years ago by
Looks like you merged #16388 first.... I will add a commit in a second.
Nathann
comment:49 Changed 7 years ago by
- Branch changed from u/vdelecroix/16370 to u/ncohen/16370
- Commit changed from bdae80af1b51e30d9bd823a8c9aba7af41325d3d to 44c01dbb4a05ee2de5ba6c427b002d606bba0b93
- Dependencies set to #16388
- Status changed from needs_work to positive_review
New commits:
767e091 | trac #16388: Specify the values of k,n in the exceptions
|
a460169 | merge Sage version 6.3.beta3
|
c365a39 | trac #16388: use format for OA + specify (k,n) for BIBD
|
ec26ca2 | trac #16388: a missing one in BIBD_from_TD
|
79178b6 | trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)
|
44c01db | trac #16370: Merged with #16388
|
comment:50 Changed 7 years ago by
- Branch changed from u/ncohen/16370 to 44c01dbb4a05ee2de5ba6c427b002d606bba0b93
- Resolution set to fixed
- Status changed from positive_review to closed
comment:51 Changed 7 years ago by
- Commit 44c01dbb4a05ee2de5ba6c427b002d606bba0b93 deleted
See #16526 for intersection graphs.
Nathann
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16370: OA(k,n) strongly regular graphs