OA(k,n) strongly regular graphs

[nathanncohen]

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

Depends on #16388

CC: @videlec @KPanComputes @dimpase @brettpim

Component: graph theory

Author: Nathann Cohen

Branch: 44c01db

Reviewer: Vincent Delecroix

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

[nathanncohen]

Branch: u/ncohen/16370

[sagetrac-git]

Commit: b35cb70

[sagetrac-git]

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

b35cb70

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

[dimpase]

comment:3

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

[sagetrac-git]

Changed commit from b35cb70 to d71f32c

[sagetrac-git]

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

d71f32c

trac #16370: Reviewer's comment

[nathanncohen]

comment:5

Done.

Nathann

[rwst]

comment:6

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

[sagetrac-git]

Changed commit from d71f32c to 57d979f

[sagetrac-git]

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

57d979f

trac #16370: Broken doc

[nathanncohen]

comment:8

Fixed !

Nathann

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

[sagetrac-git]

Changed commit from 57d979f to 90a72bd

[videlec]

comment:10

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

[nathanncohen]

comment:11

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

[KPanComputes]

comment:13

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

[videlec]

comment:14

Replying to @KPanComputes:

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

[nathanncohen]

comment:43

It would have been kind to write the commit yourself.

Anyway, here it is.

Nathann

[sagetrac-git]

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

d1e272f

trac #16370: Reviewer's comments 2

[sagetrac-git]

Changed commit from 7b73bc5 to d1e272f

[videlec]

comment:45

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

[nathanncohen]

Changed commit from d1e272f to bdae80a

[nathanncohen]

New commits:

bdae80a

trac #16370: more docs

[nathanncohen]

Changed branch from u/ncohen/16370 to u/vdelecroix/16370

[nathanncohen]

Reviewer: Vincent Delecroix

[vbraun]

comment:47

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

[nathanncohen]

comment:48

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

Nathann

[nathanncohen]

Changed commit from bdae80a to 44c01db

[nathanncohen]

Changed branch from u/vdelecroix/16370 to u/ncohen/16370

[nathanncohen]

Dependencies: #16388

[nathanncohen]

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

[vbraun]

Changed branch from u/ncohen/16370 to 44c01db

[nathanncohen]

Changed commit from 44c01db to none

[nathanncohen]

comment:51

See #16526 for intersection graphs.

Nathann