Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#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) Commit:
Dependencies: #16388 Stopgaps:

Description (last modified by vdelecroix)

Turns out that orthogonal arrays give strongly regular graphs. Isn't that cool ?

Brouwer's website is filled with references to "OA" :-)

Nathann

Change History (51)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16370
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to b35cb70af5ae6c47669d5d19a9602ff7a5267005

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

b35cb70trac #16370: OA(k,n) strongly regular graphs

comment:3 Changed 5 years ago by dimpase

please change Professor Brouwer to Andries Brouwer. Andries is against these sorts of formalities (I know him for, like 25 years).

comment:4 Changed 5 years ago by git

  • Commit changed from b35cb70af5ae6c47669d5d19a9602ff7a5267005 to d71f32cbcf327d97e4047984ae3499e0dedcae0f

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

d71f32ctrac #16370: Reviewer's comment

comment:5 Changed 5 years ago by ncohen

Done.

Nathann

comment:6 Changed 5 years ago by rws

  • 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 5 years ago by git

  • Commit changed from d71f32cbcf327d97e4047984ae3499e0dedcae0f to 57d979f22bd56536648945c3821ccf872fcfbeb9

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

57d979ftrac #16370: Broken doc

comment:8 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

Fixed !

Nathann

comment:9 Changed 5 years ago by git

  • Commit changed from 57d979f22bd56536648945c3821ccf872fcfbeb9 to 90a72bd39d74c24cb548e5b7dc5995c67ac386f8

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

90a72bdtrac #16370: OA(k,n) strongly regular graphs

comment:10 follow-up: Changed 5 years ago by vdelecroix

  • 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 5 years ago by ncohen

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 if data=k and n=n but also returns what we think if data is set to an OA?

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 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:13 follow-up: Changed 5 years ago by knsam

So, you guys decided against implementing a generic graphs.IntersectionGraph constructor?

comment:14 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by vdelecroix

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: Changed 5 years ago by 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])

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by vdelecroix

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: Changed 5 years ago by ncohen

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 5 years ago by ncohen

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: Changed 5 years ago by vdelecroix

  • 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: Changed 5 years ago by vdelecroix

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: Changed 5 years ago by knsam

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.

Last edited 5 years ago by knsam (previous) (diff)

comment:22 in reply to: ↑ 19 Changed 5 years ago by 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 of graphs.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 5 years ago by git

  • Commit changed from 90a72bd39d74c24cb548e5b7dc5995c67ac386f8 to e3c1c2180178c94d883db945dc33f2b457330cbc

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

74c30a6trac #16370: Merged with 6.3.beta2
e3c1c21trac #16370: Parameters of the SRG in the doc

comment:24 in reply to: ↑ 20 Changed 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by ncohen

  • Status changed from needs_work to needs_review

As I believe I answered all questions... O_o

Nathann

comment:27 follow-up: Changed 5 years ago by vdelecroix

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 of graphs.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 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from e3c1c2180178c94d883db945dc33f2b457330cbc to e469bb5b23d7862b48082f1cba9fd946dd7dc406

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

e469bb5trac #16370: Warnings in the constructor

comment:31 follow-ups: Changed 5 years ago by vdelecroix

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 5 years ago by ncohen

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 of graphs.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 5 years ago by ncohen

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

Last edited 5 years ago by ncohen (previous) (diff)

comment:34 Changed 5 years ago by ncohen

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: Changed 5 years ago by vdelecroix

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: Changed 5 years ago by ncohen

Yo !

As OrthogonalArrayGraph is ambiguous, what do you think of OrthogonalArrayIntersectionGraph or OrthogonalArrayBlockGraph or OrthogonalArrayBlockIntersectionGraph?

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 5 years ago by ncohen

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: Changed 5 years ago by vdelecroix

Replying to ncohen:

Yo !

As OrthogonalArrayGraph is ambiguous, what do you think of OrthogonalArrayIntersectionGraph or OrthogonalArrayBlockGraph or OrthogonalArrayBlockIntersectionGraph?

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: Changed 5 years ago by 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.

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 5 years ago by git

  • Commit changed from e469bb5b23d7862b48082f1cba9fd946dd7dc406 to 7b73bc55865f7c7bd454dd047dc38f0ed2ff58be

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

1a3255ctrac #16370: Merged with 6.3.beta3
7b73bc5trac #16370: Reviewer's comments

comment:41 in reply to: ↑ 39 Changed 5 years ago by vdelecroix

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 5 years ago by vdelecroix

  • 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 5 years ago by ncohen

  • 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 5 years ago by git

  • Commit changed from 7b73bc55865f7c7bd454dd047dc38f0ed2ff58be to d1e272f81fbd464af0f46199faa3b3fb1eda2376

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

d1e272ftrac #16370: Reviewer's comments 2

comment:45 Changed 5 years ago by vdelecroix

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 5 years ago by ncohen

  • 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:

bdae80atrac #16370: more docs

comment:47 follow-up: Changed 5 years ago by vbraun

  • 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 5 years ago by ncohen

Looks like you merged #16388 first.... I will add a commit in a second.

Nathann

comment:49 Changed 5 years ago by ncohen

  • 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:

767e091trac #16388: Specify the values of k,n in the exceptions
a460169merge Sage version 6.3.beta3
c365a39trac #16388: use format for OA + specify (k,n) for BIBD
ec26ca2trac #16388: a missing one in BIBD_from_TD
79178b6trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)
44c01dbtrac #16370: Merged with #16388

comment:50 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16370 to 44c01dbb4a05ee2de5ba6c427b002d606bba0b93
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:51 Changed 5 years ago by ncohen

  • Commit 44c01dbb4a05ee2de5ba6c427b002d606bba0b93 deleted

See #16526 for intersection graphs.

Nathann

Note: See TracTickets for help on using tickets.