OA(k,n) strongly regular graphs

[ncohen]

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

[git]

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

​b35cb70

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

[dimpase]

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

[git]

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

​d71f32c

trac #16370: Reviewer's comment

[ncohen]

Done.

Nathann

[rws]

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

[git]

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

​57d979f

trac #16370: Broken doc

[ncohen]

Fixed !

Nathann

[git]

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

[vdelecroix]

Hi Nathann,

Could you write in the docs:

• how the graph is built
• what are the parameters (v=n², 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

[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=n², 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

[knsam]

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

[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...

[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])

[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

[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

[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

[vdelecroix]

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)²+(v-1)/(k-1)-2, mu=k²

and this should be mentioned and tested.

By the way, why is there no BIBD in the Brouwer table?

Vincent

[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.

• ​http://www.win.tue.nl/~aeb/graphs/S.html.
• ​http://www.win.tue.nl/~aeb/graphs/STS.html

and even more generally, it is written that the block graph of a quasi-symmetric design is strongly regular.

Vincent

[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.

[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

[git]

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

​74c30a6	trac #16370: Merged with 6.3.beta2
​e3c1c21	trac #16370: Parameters of the SRG in the doc

[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

[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

[ncohen]

As I believe I answered all questions... O_o

Nathann

[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

[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

[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

[git]

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

​e469bb5

trac #16370: Warnings in the constructor

[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

[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

[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

[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

[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

[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

[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.

[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.

[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

[git]

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

​1a3255c	trac #16370: Merged with 6.3.beta3
​7b73bc5	trac #16370: Reviewer's comments

[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.

[vdelecroix]

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

[ncohen]

It would have been kind to write the commit yourself.

Anyway, here it is.

Nathann

[git]

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

​d1e272f

trac #16370: Reviewer's comments 2

[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

[ncohen]

New commits:

​bdae80a

trac #16370: more docs

[vbraun]

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)!

[ncohen]

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

Nathann

[ncohen]

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

[ncohen]

See #16526 for intersection graphs.

Nathann