Sage: Ticket #16370: OA(k,n) strongly regular graphs
https://trac.sagemath.org/ticket/16370
<p>
Turns out that orthogonal arrays give strongly regular graphs. Isn't that cool ?
</p>
<p>
Brouwer's website is filled with references to "OA" <code>:-)</code>
</p>
<ul><li><a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/srg/srgtab251-300.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/srg/srgtab251-300.html</a>
</li><li><a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/OA.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/OA.html</a>
</li></ul><p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16370
Trac 1.1.6ncohenSat, 17 May 2014 09:53:13 GMTstatus changed; branch set
https://trac.sagemath.org/ticket/16370#comment:1
https://trac.sagemath.org/ticket/16370#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/16370</em>
</li>
</ul>
TicketgitSat, 17 May 2014 09:53:28 GMTcommit set
https://trac.sagemath.org/ticket/16370#comment:2
https://trac.sagemath.org/ticket/16370#comment:2
<ul>
<li><strong>commit</strong>
set to <em>b35cb70af5ae6c47669d5d19a9602ff7a5267005</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b35cb70af5ae6c47669d5d19a9602ff7a5267005"><span class="icon"></span>b35cb70</a></td><td><code>trac #16370: OA(k,n) strongly regular graphs</code>
</td></tr></table>
TicketdimpaseSat, 17 May 2014 19:54:58 GMT
https://trac.sagemath.org/ticket/16370#comment:3
https://trac.sagemath.org/ticket/16370#comment:3
<p>
please change <code>Professor Brouwer</code> to <code>Andries Brouwer</code>. Andries is against these sorts of formalities (I know him for, like 25 years).
</p>
TicketgitSat, 17 May 2014 22:03:44 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:4
https://trac.sagemath.org/ticket/16370#comment:4
<ul>
<li><strong>commit</strong>
changed from <em>b35cb70af5ae6c47669d5d19a9602ff7a5267005</em> to <em>d71f32cbcf327d97e4047984ae3499e0dedcae0f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d71f32cbcf327d97e4047984ae3499e0dedcae0f"><span class="icon"></span>d71f32c</a></td><td><code>trac #16370: Reviewer's comment</code>
</td></tr></table>
TicketncohenSat, 17 May 2014 22:04:09 GMT
https://trac.sagemath.org/ticket/16370#comment:5
https://trac.sagemath.org/ticket/16370#comment:5
<p>
Done.
</p>
<p>
Nathann
</p>
TicketrwsSun, 18 May 2014 15:50:59 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:6
https://trac.sagemath.org/ticket/16370#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<pre class="wiki">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
</pre>
TicketgitSun, 18 May 2014 16:16:15 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:7
https://trac.sagemath.org/ticket/16370#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>d71f32cbcf327d97e4047984ae3499e0dedcae0f</em> to <em>57d979f22bd56536648945c3821ccf872fcfbeb9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=57d979f22bd56536648945c3821ccf872fcfbeb9"><span class="icon"></span>57d979f</a></td><td><code>trac #16370: Broken doc</code>
</td></tr></table>
TicketncohenSun, 18 May 2014 16:16:57 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:8
https://trac.sagemath.org/ticket/16370#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Fixed !
</p>
<p>
Nathann
</p>
TicketgitFri, 23 May 2014 13:15:26 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:9
https://trac.sagemath.org/ticket/16370#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>57d979f22bd56536648945c3821ccf872fcfbeb9</em> to <em>90a72bd39d74c24cb548e5b7dc5995c67ac386f8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=90a72bd39d74c24cb548e5b7dc5995c67ac386f8"><span class="icon"></span>90a72bd</a></td><td><code>trac #16370: OA(k,n) strongly regular graphs</code>
</td></tr></table>
TicketvdelecroixTue, 03 Jun 2014 10:48:44 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:10
https://trac.sagemath.org/ticket/16370#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hi Nathann,
</p>
<p>
Could you write in the docs:
</p>
<ul><li>how the graph is built
</li><li>what are the parameters (v=n<sup>2</sup>, k=k(n-1), lambda=(k-1)(k-2)+n-2, mu=k(k-1))
</li></ul><p>
Might also be good in the doctests, i.e.
</p>
<pre class="wiki">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)
</pre><p>
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 <code>def OrthogonalArrayGraph(data, n=None)</code> returning what you did if <code>data=k</code> and <code>n=n</code> but also returns what we think if <code>data</code> is set to an <code>OA</code>?
</p>
<p>
The construction is actually much more general: from any set of subsets we can build such a graph. Wikipedia calls it an <a class="ext-link" href="http://en.wikipedia.org/wiki/Intersection_graph"><span class="icon"></span>Intersection graph</a> (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 <code>graphs.IntersectionGraph</code> would make more sense.
</p>
<p>
Vincent
</p>
TicketncohenTue, 03 Jun 2014 11:00:06 GMT
https://trac.sagemath.org/ticket/16370#comment:11
https://trac.sagemath.org/ticket/16370#comment:11
<p>
Y666666666666 !!
</p>
<blockquote class="citation">
<p>
Could you write in the docs:
</p>
<ul><li>how the graph is built
</li></ul></blockquote>
<p>
Isn't that written already ?..
</p>
<pre class="wiki">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.
</pre><p>
That's a definition of the graph.
</p>
<blockquote class="citation">
<ul><li>what are the parameters (v=n<sup>2</sup>, k=k(n-1), lambda=(k-1)(k-2)+n-2, mu=k(k-1))
</li></ul></blockquote>
<p>
The parameters associated with a strongly regular graph.
</p>
<pre class="wiki">sage: Graph.is_strongly_regular??
</pre><blockquote class="citation">
<p>
Might also be good in the doctests, i.e.
</p>
<pre class="wiki">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)
</pre></blockquote>
<p>
I don't get what you want me to add.... Only a call to <code>G.vertices()</code> ? Brouwer gives the actual parameters of the final OA graph but I don't do this in the docstring, so well....
</p>
<blockquote class="citation">
<p>
The graph depends on the OA(k,n), doesn't it?
</p>
</blockquote>
<p>
Yes.
</p>
<blockquote class="citation">
<p>
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 <code>def OrthogonalArrayGraph(data, n=None)</code> returning what you did if <code>data=k</code> and <code>n=n</code> but also returns what we think if <code>data</code> is set to an <code>OA</code>?
</p>
</blockquote>
<p>
We could have a graph constructos <code>graphs.IntersectionGraph</code> taking as an argument a list of sets and returning the corresponding graph. Would make more sense than a dedicated version for OA.
</p>
<blockquote class="citation">
<p>
The construction is actually much more general: from any set of subsets we can build such a graph. Wikipedia calls it an <a class="ext-link" href="http://en.wikipedia.org/wiki/Intersection_graph"><span class="icon"></span>Intersection graph</a> (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 <code>graphs.IntersectionGraph</code> would make more sense.
</p>
</blockquote>
<p>
Ahem. I should read the email before I answer them. Indeed, indeed <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenTue, 03 Jun 2014 11:36:29 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:12
https://trac.sagemath.org/ticket/16370#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketknsamTue, 03 Jun 2014 11:44:35 GMT
https://trac.sagemath.org/ticket/16370#comment:13
https://trac.sagemath.org/ticket/16370#comment:13
<p>
So, you guys decided against implementing a generic <code>graphs.IntersectionGraph</code> constructor?
</p>
TicketvdelecroixTue, 03 Jun 2014 11:45:56 GMT
https://trac.sagemath.org/ticket/16370#comment:14
https://trac.sagemath.org/ticket/16370#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:13" title="Comment 13">knsam</a>:
</p>
<blockquote class="citation">
<p>
So, you guys decided against implementing a generic <code>graphs.IntersectionGraph</code> constructor?
</p>
</blockquote>
<p>
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...
</p>
TicketncohenTue, 03 Jun 2014 12:00:44 GMT
https://trac.sagemath.org/ticket/16370#comment:15
https://trac.sagemath.org/ticket/16370#comment:15
<blockquote class="citation">
<blockquote class="citation">
<p>
So, you guys decided against implementing a generic <code>graphs.IntersectionGraph</code> constructor?
</p>
</blockquote>
<p>
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...
</p>
</blockquote>
<p>
Yep yep... Actually creating this constructor can be useful... Right now you can build such graphs easily but nobody knows the syntax :
</p>
<pre class="wiki">sage: random_sets = [Subsets(range(15)).random_element() for _ in range(15)]
sage: g = Graph([random_sets,lambda x,y : x&y])
</pre>
TicketvdelecroixTue, 03 Jun 2014 16:39:02 GMT
https://trac.sagemath.org/ticket/16370#comment:16
https://trac.sagemath.org/ticket/16370#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
So, you guys decided against implementing a generic <code>graphs.IntersectionGraph</code> constructor?
</p>
</blockquote>
<p>
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...
</p>
</blockquote>
<p>
Yep yep... Actually creating this constructor can be useful... Right now you can build such graphs easily but nobody knows the syntax :
</p>
<pre class="wiki">sage: random_sets = [Subsets(range(15)).random_element() for _ in range(15)]
sage: g = Graph([random_sets,lambda x,y : x&y])
</pre></blockquote>
<p>
Hi,
</p>
<p>
So, what is the point of the ticket if we can already do
</p>
<pre class="wiki">sage: g = Graph([map(Set, designs.transversal_design(3,7)), lambda x,y : x&y])
</pre><p>
Moreover, the graph you obtain is also strongly regular with BIBD input
</p>
<pre class="wiki">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)
</pre><p>
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 <code>graphs.IntersectionGraph</code>.
</p>
<p>
Vincent
</p>
TicketncohenTue, 03 Jun 2014 16:44:01 GMT
https://trac.sagemath.org/ticket/16370#comment:17
https://trac.sagemath.org/ticket/16370#comment:17
<p>
Yo !
</p>
<blockquote class="citation">
<p>
So, what is the point of the ticket if we can already do
</p>
<pre class="wiki">sage: g = Graph([map(Set, designs.transversal_design(3,7)), lambda x,y : x&y])
</pre></blockquote>
<p>
Several points :
</p>
<p>
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
</p>
<p>
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
</p>
<p>
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
</p>
<p>
4) We both agree that we needs a <code>graphs.IntersectionGraph</code> function because the syntax above is not very natural, don't tell me now that user should find it by themselves <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Moreover, the graph you obtain is also strongly regular with BIBD input
</p>
<pre class="wiki">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)
</pre></blockquote>
<p>
Err... Well, this is actually a bug report. The parameters must always be positive. Will look at it right now.
</p>
<blockquote class="citation">
<p>
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 <code>graphs.IntersectionGraph</code>.
</p>
</blockquote>
<p>
Tell me if my answers above convinced you.
</p>
<p>
Nathann
</p>
TicketncohenTue, 03 Jun 2014 17:07:12 GMT
https://trac.sagemath.org/ticket/16370#comment:18
https://trac.sagemath.org/ticket/16370#comment:18
<blockquote class="citation">
<p>
Err... Well, this is actually a bug report. The parameters must always be positive. Will look at it right now.
</p>
</blockquote>
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/16433" title="defect: clique_with_loops.is_strongly_regular() is True (closed: fixed)">#16433</a>. 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.
</p>
<p>
It is an exception in the definition.
</p>
<p>
A stupid one.
</p>
<p>
Anyway.
</p>
<p>
Nathann
</p>
TicketvdelecroixTue, 03 Jun 2014 19:51:47 GMTstatus, description changed
https://trac.sagemath.org/ticket/16370#comment:19
https://trac.sagemath.org/ticket/16370#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/16370?action=diff&version=19">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:17" title="Comment 17">ncohen</a>:
</p>
<blockquote class="citation">
<p>
[...]
</p>
<p>
Tell me if my answers above convinced you.
</p>
</blockquote>
<p>
Yes: this ticket should not go without a <code>graphs.IntersectionGraph</code>. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc of <code>graphs.IntersectionGraph</code>.
</p>
<p>
For the parameters: they are explicit in terms of (k,n) for TD and (v,k) for BIBD.
</p>
<ul><li>for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
</li><li>for BIBD(v,k): lambda=(k-1)<sup>2</sup>+(v-1)/(k-1)-2, mu=k<sup>2</sup>
</li></ul><p>
and this should be mentioned and tested.
</p>
<p>
By the way, why is there no BIBD in the Brouwer table?
</p>
<p>
Vincent
</p>
TicketvdelecroixWed, 04 Jun 2014 08:32:29 GMT
https://trac.sagemath.org/ticket/16370#comment:20
https://trac.sagemath.org/ticket/16370#comment:20
<p>
Hi there,
</p>
<p>
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 <code>graphs.SteinerDesignGraph</code> instead of a BIBD one. More generally all Steiner systems give strongly regular graphs.
</p>
<ul><li><a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/S.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/S.html</a>.
</li><li><a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/STS.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/STS.html</a>
</li></ul><p>
and even more generally, it is written that <em>the block graph of a quasi-symmetric design is strongly regular.</em>
</p>
<p>
Vincent
</p>
TicketknsamWed, 04 Jun 2014 09:02:58 GMT
https://trac.sagemath.org/ticket/16370#comment:21
https://trac.sagemath.org/ticket/16370#comment:21
<p>
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:
</p>
<ul><li>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.
</li></ul><ul><li>Adjacency graph: the points are the vertices; two vertices are adjacent if they are incident in a common line.
</li></ul><ul><li>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.
</li></ul><p>
As I indicated above, it is common to call the graphs that we are talking about as Block intersection graphs.
</p>
<p>
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.
</p>
<p>
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 <a class="ext-link" href="http://sina.sharif.edu/~emahmood/papers/MR1147979.PDF"><span class="icon"></span>here</a>.
</p>
<p>
Hope this is helpful.
</p>
TicketncohenWed, 04 Jun 2014 11:16:54 GMT
https://trac.sagemath.org/ticket/16370#comment:22
https://trac.sagemath.org/ticket/16370#comment:22
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Yes: this ticket should not go without a <code>graphs.IntersectionGraph</code>. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc of <code>graphs.IntersectionGraph</code>.
</p>
</blockquote>
<p>
Intersection graphs are something we should add, but it is not a dependency of this ticket so it will be done elsewhere.
</p>
<blockquote class="citation">
<ul><li>for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
</li></ul></blockquote>
<p>
I added a line about that in the construction of the orthogonal array graph, see commits.
</p>
<blockquote class="citation">
<p>
By the way, why is there no BIBD in the Brouwer table?
</p>
</blockquote>
<p>
This has been solved, Vincent sent an email to Brouwer.
</p>
<p>
Nathann
</p>
TicketgitWed, 04 Jun 2014 11:20:44 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:23
https://trac.sagemath.org/ticket/16370#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>90a72bd39d74c24cb548e5b7dc5995c67ac386f8</em> to <em>e3c1c2180178c94d883db945dc33f2b457330cbc</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=74c30a6810511eaf5f613713e4f1f88f44fee33d"><span class="icon"></span>74c30a6</a></td><td><code>trac #16370: Merged with 6.3.beta2</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e3c1c2180178c94d883db945dc33f2b457330cbc"><span class="icon"></span>e3c1c21</a></td><td><code>trac #16370: Parameters of the SRG in the doc</code>
</td></tr></table>
TicketncohenWed, 04 Jun 2014 11:26:24 GMT
https://trac.sagemath.org/ticket/16370#comment:24
https://trac.sagemath.org/ticket/16370#comment:24
<p>
Yo !
</p>
<blockquote class="citation">
<p>
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 <code>graphs.SteinerDesignGraph</code> instead of a BIBD one. More generally all Steiner systems give strongly regular graphs.
</p>
</blockquote>
<p>
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.
</p>
<p>
Which is also why I do not like "<a class="missing wiki">SteinerDesignGraph?</a>" but at the very least "Steiner2DesignGraph", even though it "contradicts the terminology" we already use, i.e. BIBD.
</p>
<p>
Nathann
</p>
TicketncohenWed, 04 Jun 2014 11:30:44 GMT
https://trac.sagemath.org/ticket/16370#comment:25
https://trac.sagemath.org/ticket/16370#comment:25
<p>
Yo !
</p>
<blockquote class="citation">
<p>
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:
</p>
</blockquote>
<p>
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 <code>:-P</code>
</p>
<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.
</p>
<p>
Thus, we need a constructor for these particular strongly regular graphs. AND we will need to add a <a class="missing wiki">BlockDesign?</a>.intersection_graph someday along with the others
</p>
<blockquote class="citation">
<p>
Hope this is helpful.
</p>
</blockquote>
<p>
Yep yep. It was a discussion about user interface almost from the beginning.
</p>
<p>
Nathann
</p>
TicketncohenWed, 04 Jun 2014 11:41:52 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:26
https://trac.sagemath.org/ticket/16370#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
As I believe I answered all questions... <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 04 Jun 2014 11:48:56 GMT
https://trac.sagemath.org/ticket/16370#comment:27
https://trac.sagemath.org/ticket/16370#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:22" title="Comment 22">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Yes: this ticket should not go without a <code>graphs.IntersectionGraph</code>. And intersection graphs of non-trivial BIBD are regular graph. So it is worth to have them at least in the doc of <code>graphs.IntersectionGraph</code>.
</p>
</blockquote>
<p>
Intersection graphs are something we should add, but it is not a dependency of this ticket so it will be done elsewhere.
</p>
</blockquote>
<p>
All right. But as Brouwer said himself in his answer it would be much more consistent to have
</p>
<pre class="wiki">sage: designs.MyPreferedDesign(x,y,z).block_intersection_graph()
</pre><p>
and not
</p>
<pre class="wiki">sage: graphs.BlockIntersectionGraphFromMyPreferedDesign(x,y,z)
</pre><blockquote class="citation">
<blockquote class="citation">
<ul><li>for TD(k,n): lambda=(k-1)(k-2)+n-2, mu=k(k-1)
</li></ul></blockquote>
<p>
I added a line about that in the construction of the orthogonal array graph, see commits.
</p>
</blockquote>
<p>
hum: k=k(n-1)
</p>
<p>
I see two more obstructions right now:
</p>
<ul><li>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.
</li><li>the function <code>designs.orthogonal_array</code> 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.
</li></ul><p>
Vincent
</p>
TicketncohenWed, 04 Jun 2014 12:05:23 GMT
https://trac.sagemath.org/ticket/16370#comment:28
https://trac.sagemath.org/ticket/16370#comment:28
<p>
Yo !
</p>
<blockquote class="citation">
<p>
All right. But as Brouwer said himself in his answer it would be much more consistent to have
</p>
<pre class="wiki">sage: designs.MyPreferedDesign(x,y,z).block_intersection_graph()
</pre></blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
and not
</p>
<pre class="wiki">sage: graphs.BlockIntersectionGraphFromMyPreferedDesign(x,y,z)
</pre></blockquote>
<p>
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 <code>graph.*</code>, 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 <code>words.ThueMorseWord</code> and <code>words.FixedPointOfMorphism</code> ?
</p>
<blockquote class="citation">
<p>
hum: k=k(n-1)
</p>
</blockquote>
<p>
Ahah. Yeah, I know. I tried to phrase it to avoid confusions, but .... yeah <code>:-P</code>
</p>
<p>
If you see another way..
</p>
<blockquote class="citation">
<p>
I see two more obstructions right now:
</p>
<ul><li>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.
</li></ul></blockquote>
<p>
No problem. I can even add that it may change between versions of Sage.
</p>
<blockquote class="citation">
<ul><li>the function <code>designs.orthogonal_array</code> 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.
</li></ul></blockquote>
<p>
A disaster indeed. I will mention that too in a second.
</p>
<p>
Nathann
</p>
TicketncohenWed, 04 Jun 2014 12:18:19 GMT
https://trac.sagemath.org/ticket/16370#comment:29
https://trac.sagemath.org/ticket/16370#comment:29
<p>
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 <code>:-P</code>
</p>
<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.
</p>
<p>
And if some construction requires a specific OA, well, they will have to explain it somewhere an we can then implement it.
</p>
<p>
Branch updated !
</p>
<p>
Nathann
</p>
TicketgitWed, 04 Jun 2014 12:18:37 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:30
https://trac.sagemath.org/ticket/16370#comment:30
<ul>
<li><strong>commit</strong>
changed from <em>e3c1c2180178c94d883db945dc33f2b457330cbc</em> to <em>e469bb5b23d7862b48082f1cba9fd946dd7dc406</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e469bb5b23d7862b48082f1cba9fd946dd7dc406"><span class="icon"></span>e469bb5</a></td><td><code>trac #16370: Warnings in the constructor</code>
</td></tr></table>
TicketvdelecroixWed, 04 Jun 2014 14:01:57 GMT
https://trac.sagemath.org/ticket/16370#comment:31
https://trac.sagemath.org/ticket/16370#comment:31
<p>
Hi,
</p>
<p>
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 <code>graphs.OrthogonalArrayGraph</code> completely misleading.
</p>
<p>
About the syntax, let me cite Andries Brouwer:
</p>
<blockquote>
<p>
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.
</p>
</blockquote>
<blockquote>
<p>
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
</p>
</blockquote>
<p>
So the name could be either <code>graphs.IntersectionGraphOfOneOrthogonalArray</code> or simply a subcase of <code>graphs.IntersectionGraph</code>. And I am in favour of the second one.
</p>
<p>
Vincent
</p>
TicketncohenWed, 04 Jun 2014 14:17:17 GMT
https://trac.sagemath.org/ticket/16370#comment:32
https://trac.sagemath.org/ticket/16370#comment:32
<blockquote class="citation">
<p>
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 <code>graphs.OrthogonalArrayGraph</code> completely misleading.
</p>
</blockquote>
<p>
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 !
</p>
<blockquote class="citation">
<p>
About the syntax, let me cite Andries Brouwer:
</p>
</blockquote>
<p>
Be honest and also copy/paste the answer I gave him.
</p>
<blockquote class="citation">
<blockquote>
<p>
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.
</p>
</blockquote>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<blockquote>
<p>
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
</p>
</blockquote>
</blockquote>
<p>
Copy/paste my answer to that. Or create a ticket to remove the words from <code>words.*</code> which can be obtained through <code>words.FixedPointOfMorphism</code>.
</p>
<p>
THIS DOES NOT MAKE ANY F<strong></strong><strong>* SENSE !
</strong></p>
<blockquote class="citation">
<p>
So the name could be either <code>graphs.IntersectionGraphOfOneOrthogonalArray</code> or simply a subcase of <code>graphs.IntersectionGraph</code>. And I am in favour of the second one.
</p>
</blockquote>
<p>
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.
</p>
<p>
Nathann
</p>
TicketncohenWed, 04 Jun 2014 15:46:33 GMT
https://trac.sagemath.org/ticket/16370#comment:33
https://trac.sagemath.org/ticket/16370#comment:33
<p>
Okay, as you quoted his email but did not quote what I answered to him I paste it here.
</p>
<hr />
<blockquote class="citation">
<blockquote>
<p>
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.
</p>
</blockquote>
<blockquote>
<p>
It makes no sense to design a system where intersection graph gets different names depending on the type of design one used as input.
</p>
</blockquote>
</blockquote>
<p>
It does.
</p>
<p>
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 <code>graphs.PetersenGraph</code> and a <code>graphs.KneserGraph</code> function.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
<hr />
<p>
Nathann
</p>
TicketncohenThu, 05 Jun 2014 06:32:34 GMT
https://trac.sagemath.org/ticket/16370#comment:34
https://trac.sagemath.org/ticket/16370#comment:34
<p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
What can I do to get this in ?
</p>
<p>
Nathann
</p>
TicketvdelecroixThu, 05 Jun 2014 08:13:11 GMT
https://trac.sagemath.org/ticket/16370#comment:35
https://trac.sagemath.org/ticket/16370#comment:35
<p>
Hi Nathann,
</p>
<p>
As <code>OrthogonalArrayGraph</code> is ambiguous, what do you think of <code>OrthogonalArrayIntersectionGraph</code> or <code>OrthogonalArrayBlockGraph</code> or <code>OrthogonalArrayBlockIntersectionGraph</code>?
</p>
<p>
At least, allow the function to be fed with an OA as I suggested in <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:10" title="Comment 10">comment:10</a>.
</p>
<pre class="wiki">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
...
</pre><p>
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
</p>
<p>
Vincent
</p>
TicketncohenThu, 05 Jun 2014 08:22:01 GMT
https://trac.sagemath.org/ticket/16370#comment:36
https://trac.sagemath.org/ticket/16370#comment:36
<p>
Yo !
</p>
<blockquote class="citation">
<p>
As <code>OrthogonalArrayGraph</code> is ambiguous, what do you think of <code>OrthogonalArrayIntersectionGraph</code> or <code>OrthogonalArrayBlockGraph</code> or <code>OrthogonalArrayBlockIntersectionGraph</code>?
</p>
</blockquote>
<p>
This graph is not the intersection graph of the blocks of an OA. If you insist, I prefer <code>designs.OrthogonalArrayBlockGraph</code>, because to me 'block' has absolutely no meaning in this context.
</p>
<blockquote class="citation">
<p>
At least, allow the function to be fed with an OA as I suggested in <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:10" title="Comment 10">comment:10</a>.
</p>
</blockquote>
<p>
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 <code>graphs.IntersectionGraph(designs.orthogonal_array(k,n))</code> would not give the same result.
</p>
<blockquote class="citation">
<p>
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
</p>
</blockquote>
<p>
I can relabel an OA. The graphs will be isomorphic but different.
</p>
<p>
Nathann
</p>
TicketncohenThu, 05 Jun 2014 08:23:23 GMT
https://trac.sagemath.org/ticket/16370#comment:37
https://trac.sagemath.org/ticket/16370#comment:37
<p>
Let me add that I don't see how "<code>graphs.OrthogonalArrayGraph</code>" is more ambiguous than "<code>graphs.OrthogonalArrayBlockGraph</code>", but at least it is not plainly wrong like the other names.
</p>
TicketvdelecroixThu, 05 Jun 2014 08:36:29 GMT
https://trac.sagemath.org/ticket/16370#comment:38
https://trac.sagemath.org/ticket/16370#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:36" title="Comment 36">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yo !
</p>
<blockquote class="citation">
<p>
As <code>OrthogonalArrayGraph</code> is ambiguous, what do you think of <code>OrthogonalArrayIntersectionGraph</code> or <code>OrthogonalArrayBlockGraph</code> or <code>OrthogonalArrayBlockIntersectionGraph</code>?
</p>
</blockquote>
<p>
This graph is not the intersection graph of the blocks of an OA. If you insist, I prefer <code>graphs.OrthogonalArrayBlockGraph</code>, because to me 'block' has absolutely no meaning in this context.
</p>
</blockquote>
<p>
You meant <code>intersection</code> has no meaning ? It depends on how you see the blocks. If you consider them as subsets of {0,...,n-1}<sup>k</sup> then it is the intersection graph of the blocks.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
At least, allow the function to be fed with an OA as I suggested in <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:10" title="Comment 10">comment:10</a>.
</p>
</blockquote>
<p>
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 <code>graphs.IntersectionGraph(designs.orthogonal_array(k,n))</code> would not give the same result.
</p>
</blockquote>
<p>
Right.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
And, if possible, give examples of two OA with the same parameters that yield to two different intersection graphs...
</p>
</blockquote>
<p>
I can relabel an OA. The graphs will be isomorphic but different.
</p>
</blockquote>
<p>
Of course, I meant non-isomorphic.
</p>
TicketncohenThu, 05 Jun 2014 08:46:14 GMT
https://trac.sagemath.org/ticket/16370#comment:39
https://trac.sagemath.org/ticket/16370#comment:39
<blockquote class="citation">
<p>
You meant <code>intersection</code> has no meaning ? It depends on how you see the blocks.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
If you consider them as subsets of {0,...,n-1}<sup>k</sup> then it is the intersection graph of the blocks.
</p>
</blockquote>
<p>
I would be delighted to hear how you define such an operation, but let's get this done first.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I can relabel an OA. The graphs will be isomorphic but different.
</p>
</blockquote>
<p>
Of course, I meant non-isomorphic.
</p>
</blockquote>
<p>
I just finished the job for "different OA". If you want non-isomorphic OA provide them.
</p>
<p>
Nathann
</p>
TicketgitThu, 05 Jun 2014 08:46:24 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:40
https://trac.sagemath.org/ticket/16370#comment:40
<ul>
<li><strong>commit</strong>
changed from <em>e469bb5b23d7862b48082f1cba9fd946dd7dc406</em> to <em>7b73bc55865f7c7bd454dd047dc38f0ed2ff58be</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1a3255c469bfe3c7f01a56e5c7ec3fbde56f047d"><span class="icon"></span>1a3255c</a></td><td><code>trac #16370: Merged with 6.3.beta3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7b73bc55865f7c7bd454dd047dc38f0ed2ff58be"><span class="icon"></span>7b73bc5</a></td><td><code>trac #16370: Reviewer's comments</code>
</td></tr></table>
TicketvdelecroixThu, 05 Jun 2014 08:55:14 GMT
https://trac.sagemath.org/ticket/16370#comment:41
https://trac.sagemath.org/ticket/16370#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16370#comment:39" title="Comment 39">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
You meant <code>intersection</code> has no meaning ? It depends on how you see the blocks.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
If you consider them as subsets of {0,...,n-1}<sup>k</sup> then it is the intersection graph of the blocks.
</p>
</blockquote>
<p>
I would be delighted to hear how you define such an operation, but let's get this done first.
</p>
</blockquote>
<p>
Sorry, I should have said "disjoint union" instead of "product".
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
I can relabel an OA. The graphs will be isomorphic but different.
</p>
</blockquote>
<p>
Of course, I meant non-isomorphic.
</p>
</blockquote>
<p>
I just finished the job for "different OA". If you want non-isomorphic OA provide them.
</p>
</blockquote>
<p>
Let me work for a minute.
</p>
TicketvdelecroixThu, 05 Jun 2014 09:38:45 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:42
https://trac.sagemath.org/ticket/16370#comment:42
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Examples with OA(3,4)
</p>
<pre class="wiki">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
</pre><p>
And actually they are quite different
</p>
<pre class="wiki">sage: g0.automorphism_group().order()
1152
sage: g1.automorphism_group().order()
192
</pre>
TicketncohenThu, 05 Jun 2014 09:46:13 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:43
https://trac.sagemath.org/ticket/16370#comment:43
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
It would have been kind to write the commit yourself.
</p>
<p>
Anyway, here it is.
</p>
<p>
Nathann
</p>
TicketgitThu, 05 Jun 2014 09:46:29 GMTcommit changed
https://trac.sagemath.org/ticket/16370#comment:44
https://trac.sagemath.org/ticket/16370#comment:44
<ul>
<li><strong>commit</strong>
changed from <em>7b73bc55865f7c7bd454dd047dc38f0ed2ff58be</em> to <em>d1e272f81fbd464af0f46199faa3b3fb1eda2376</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d1e272f81fbd464af0f46199faa3b3fb1eda2376"><span class="icon"></span>d1e272f</a></td><td><code>trac #16370: Reviewer's comments 2</code>
</td></tr></table>
TicketvdelecroixThu, 05 Jun 2014 10:19:12 GMT
https://trac.sagemath.org/ticket/16370#comment:45
https://trac.sagemath.org/ticket/16370#comment:45
<p>
Hi,
</p>
<p>
Two non-isomorphic OA(k,n) might give isomorphic intersection graph (exercise ;-P). I modified the documentation accordingly.
</p>
<p>
I put a <code>k'</code> for the parameters of the srg to avoid ambiguity with the <code>k</code> of the TD.
</p>
<p>
I exchanged the 1 and 2 in the last column of <code>oa1</code>, that way it looks closer to <code>oa0</code>.
</p>
<p>
The graph <code>g0</code> is actually an affine polar graph, I added it to the documentation. I tried other constructions mentioned in the Brouwer table to find <code></code>g1<code></code> but I did not succeed.
</p>
<p>
Have a look at u/vdelecroix/16370. Tests pass and documentation build so set to positive review after my commit if you like it.
</p>
<p>
Vincent
</p>
TicketncohenThu, 05 Jun 2014 10:40:14 GMTstatus, branch, commit changed; reviewer set
https://trac.sagemath.org/ticket/16370#comment:46
https://trac.sagemath.org/ticket/16370#comment:46
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/16370</em> to <em>u/vdelecroix/16370</em>
</li>
<li><strong>commit</strong>
changed from <em>d1e272f81fbd464af0f46199faa3b3fb1eda2376</em> to <em>bdae80af1b51e30d9bd823a8c9aba7af41325d3d</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bdae80af1b51e30d9bd823a8c9aba7af41325d3d"><span class="icon"></span>bdae80a</a></td><td><code>trac #16370: more docs</code>
</td></tr></table>
TicketvbraunThu, 05 Jun 2014 13:56:42 GMTstatus changed
https://trac.sagemath.org/ticket/16370#comment:47
https://trac.sagemath.org/ticket/16370#comment:47
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<pre class="wiki">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)!
</pre>
TicketncohenThu, 05 Jun 2014 14:04:42 GMT
https://trac.sagemath.org/ticket/16370#comment:48
https://trac.sagemath.org/ticket/16370#comment:48
<p>
Looks like you merged <a class="closed ticket" href="https://trac.sagemath.org/ticket/16388" title="enhancement: Specify the values of k,n in the exceptions (closed: fixed)">#16388</a> first.... I will add a commit in a second.
</p>
<p>
Nathann
</p>
TicketncohenThu, 05 Jun 2014 14:08:57 GMTstatus, commit, branch changed; dependencies set
https://trac.sagemath.org/ticket/16370#comment:49
https://trac.sagemath.org/ticket/16370#comment:49
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>commit</strong>
changed from <em>bdae80af1b51e30d9bd823a8c9aba7af41325d3d</em> to <em>44c01dbb4a05ee2de5ba6c427b002d606bba0b93</em>
</li>
<li><strong>dependencies</strong>
set to <em>#16388</em>
</li>
<li><strong>branch</strong>
changed from <em>u/vdelecroix/16370</em> to <em>u/ncohen/16370</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=767e0911107e5b374ad182acd0e5dac79ae8c874"><span class="icon"></span>767e091</a></td><td><code>trac #16388: Specify the values of k,n in the exceptions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a46016940e56a1d56bb0542c1320f87c057862da"><span class="icon"></span>a460169</a></td><td><code>merge Sage version 6.3.beta3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c365a39d76ea00e63e1f11de86ad3474fc3f77b9"><span class="icon"></span>c365a39</a></td><td><code>trac #16388: use format for OA + specify (k,n) for BIBD</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ec26ca23d2549d6dc111c6d69d03df739115ee9f"><span class="icon"></span>ec26ca2</a></td><td><code>trac #16388: a missing one in BIBD_from_TD</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=79178b62b55c9d38b4ee015118e1cbc6acefb8f8"><span class="icon"></span>79178b6</a></td><td><code>trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=44c01dbb4a05ee2de5ba6c427b002d606bba0b93"><span class="icon"></span>44c01db</a></td><td><code>trac #16370: Merged with #16388</code>
</td></tr></table>
TicketvbraunFri, 06 Jun 2014 18:08:02 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16370#comment:50
https://trac.sagemath.org/ticket/16370#comment:50
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/16370</em> to <em>44c01dbb4a05ee2de5ba6c427b002d606bba0b93</em>
</li>
</ul>
TicketncohenTue, 24 Jun 2014 15:21:40 GMTcommit deleted
https://trac.sagemath.org/ticket/16370#comment:51
https://trac.sagemath.org/ticket/16370#comment:51
<ul>
<li><strong>commit</strong>
<em>44c01dbb4a05ee2de5ba6c427b002d606bba0b93</em> deleted
</li>
</ul>
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/16526" title="enhancement: IntersectionGraph constructor (closed: fixed)">#16526</a> for intersection graphs.
</p>
<p>
Nathann
</p>
Ticket