implement Taylor 2-graphs for U_3(q) and related srg's

[dimpase]

implement Taylor 2-graphs for U_3(q) and related srg's; the latter have to be constructed directly, as the two-graph gets very big and slow.

see §7E of ​Brouwer and van Lint and note the ​correction saying

§7E, A construction by D. Taylor, it should say: ... "the triples {x,y,z} for which H(x,y)H(y,z)H(z,x) is a square in GF(q^2) if q ≡ 3 mod 4, a nonsquare if q ≡ 1 mod 4"

[dimpase]

also improve __init__ of TwoGraph, using **kwds.

[dimpase]

Last 10 new commits:

​ab18d25	merge Merge branch 'unitary' into the latest #18972
​5450f1e	doctest fixes from John Palmieri: Thanks John! They help!
​50a6efc	Merge branch 'seidelsw' into unitary
​35a9b17	doctest fixes
​fd9a689	Merge branch 'seidelsw' into unitary
​acc985a	addressed reviewer's points
​ee9c5d6	address #18997:24
​88ed777	Merge branch 'develop' into unitary
​ce952f9	Merge branch 'unitary' into taylor2graphs
​ef096b5	implement the constructions of SRGs on q^3 and q^3+1 points

[git]

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

​56d98a3	trac #19099: Always check output in strongly_regular_graph
​52b5559	Merge branch 'u/ncohen/19099' of git://trac.sagemath.org/sage into taylor2graphs

[dimpase]

New commits:

​56d98a3	trac #19099: Always check output in strongly_regular_graph
​52b5559	Merge branch 'u/ncohen/19099' of git://trac.sagemath.org/sage into taylor2graphs

---

New commits:

​56d98a3	trac #19099: Always check output in strongly_regular_graph
​52b5559	Merge branch 'u/ncohen/19099' of git://trac.sagemath.org/sage into taylor2graphs

[git]

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

​1cf1066	replace duplicate [vLintBrouwer84] with [BvL84]
​9758eb6	recongintion of Taylor 2-graph srg. 6 more graphs in!

[git]

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

​773d10d

more doctests and docs and typos fixed

[dimpase]

I don't grok that **kwds business; the following does not work:

diff --git a/src/sage/combinat/designs/twographs.py b/src/sage/combinat/designs/twographs.py
index c86506b..d3b51c8 100644
--- a/src/sage/combinat/designs/twographs.py
+++ b/src/sage/combinat/designs/twographs.py
@@ -68,8 +68,7 @@ class TwoGraph(IncidenceStructure):
     :mod:`~sage.combinat.designs.twographs` module.
 
     """
-    def __init__(self, points=None, blocks=None, incidence_matrix=None,
-            name=None, check=False, copy=True):
+    def __init__(self, check=False, **kwds):
         r"""
         Constructor of the class
 
@@ -86,9 +85,7 @@ class TwoGraph(IncidenceStructure):
             sage: TwoGraph(p, check=True)
             Incidence structure with 10 points and 60 blocks
         """
-        IncidenceStructure.__init__(self, points=points, blocks=blocks,
-                                    incidence_matrix=incidence_matrix,
-                                    name=name, check=False, copy=copy)
+        IncidenceStructure.__init__(self, check=False, **kwds)
         if check:  # it is a very slow, O(|points|^4), test...
            from sage.combinat.designs.twographs import is_twograph
            assert is_twograph(self), "the structure is not a 2-graph!"

Any idea? Otherwise, the ticket is ready...

[ncohen]

Any idea? Otherwise, the ticket is ready...

What do you think of bug reports which say "that does not work" and do not say what's wrong?

[chapoton]

doc does not build, see patchbot report

[dimpase]

Replying to ncohen:

Any idea? Otherwise, the ticket is ready...

What do you think of bug reports which say "that does not work" and do not say what's wrong?

well, I was wondering whether what I tried was totally silly... Anyhow, here is what I get after this change:

sage -t twographs.py
**********************************************************************
File "twographs.py", line 78, in sage.combinat.designs.twographs.TwoGraph.__init__
Failed example:
    TwoGraph([[1,2]])
Exception raised:
    Traceback (most recent call last):
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.designs.twographs.TwoGraph.__init__[1]>", line 1, in <module>
        TwoGraph([[Integer(1),Integer(2)]])
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/combinat/designs/twographs.py", line 88, in __init__
        IncidenceStructure.__init__(self, check=False, **kwds)
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/combinat/designs/incidence_structures.py", line 241, in __init__
        self._points = sorted(points)
    TypeError: 'NoneType' object is not iterable
**********************************************************************
File "twographs.py", line 80, in sage.combinat.designs.twographs.TwoGraph.__init__
Failed example:
    TwoGraph([[1,2]], check=True)
Expected:
    Traceback (most recent call last):
    ...
    AssertionError: the structure is not a 2-graph!
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/dima/software/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.designs.twographs.TwoGraph.__init__[2]>", line 1, in <module>
        TwoGraph([[Integer(1),Integer(2)]], check=True)
    TypeError: __init__() got multiple values for keyword argument 'check'
**********************************************************************
File "twographs.py", line 84, in sage.combinat.designs.twographs.TwoGraph.__init__
Failed example:
    p=graphs.PetersenGraph().twograph()
...

[git]

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

​bc401ce

satisfied sphinx (bug shows only after make doc-clean)

[ncohen]

What is this ? O_o

+- cf. ``git blame`` for the others involved

Nathann

[dimpase]

Replying to ncohen:

What is this ? O_o

+- cf. ``git blame`` for the others involved

What, your legal department does not approve this copyright notice?

[dimpase]

of course I can remove it if you like...

[ncohen]

What, your legal department does not approve this copyright notice?

It committed suicide last month, but through an exorcist I was able to get in touch with one of its members: what about just removing the only entry that exists in this file, given that it is not representative of anything, instead of leaving it alone and adding your note?

Nathann

[git]

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

​86495a4

authors cleared

[dimpase]

Replying to ncohen:

What, your legal department does not approve this copyright notice?

It committed suicide last month, but through an exorcist I was able to get in touch with one of its members: what about just removing the only entry that exists in this file, given that it is not representative of anything, instead of leaving it alone and adding your note?

be my guest.

[git]

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

​edb886e

authors cleared

[ncohen]

Sorry but I can't review this branch before its dependencies get merged. I'm trying to get the 'diff' file while excluding dependencies, but I can't obtain *only* what this branch changes...

Nathann

[ncohen]

+    Test whether some Taylor two-graph SRG is `(v,k,\lambda,\mu)`-strongly regular.
+
+    For more information, see http://www.win.tue.nl/~aeb/graphs/srghub.html.

I don't find "Taylor" in that page.

Nathann

[git]

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

​6262d65

give the right references, and also the typo missed earlier

[dimpase]

Replying to ncohen:

+    Test whether some Taylor two-graph SRG is `(v,k,\lambda,\mu)`-strongly regular.
+
+    For more information, see http://www.win.tue.nl/~aeb/graphs/srghub.html.

I don't find "Taylor" in that page.e

fixed by the last commit.

[dimpase]

Replying to git:

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

​edb886e

authors cleared

this commit did not change anything. Fixed in the last commit.

[git]

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

​685d86d

utf-8...

[git]

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

​dbca37e

a sporadic example related to 2-graphs

[git]

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

​302e6bc	trac #19133: Three Witt-based strongly regular graphs
​6a6f7b3	Merge remote-tracking branch 'trac/public/19133' into taylor2graphs

[ncohen]

Good news: a new beta has been released, so I will be able to review this soon

Bad news: it is in conflcit with the latest beta :-/

Nathann

[git]

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

​d7878be

Merge branch 'taylor2graphs' into tay2

[dimpase]

Replying to git:

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

​d7878be

Merge branch 'taylor2graphs' into tay2

rebased over the latest beta

[ncohen]

I pushed a speedup at public/19098.

Nathann

[ncohen]

Helloooooooooo Dima,

Two questions about this branch:

• It seems that you do not use the taylor_twograph function anywhere. If you think that it is useful in its own right I do not mind, but I couldn't help but notice the apparently large overlap between the code of taylor_twograph and the code of TaylorTwographDescendantSRG. Couldn't you let one of the two functions call the other? Especially since with the speedup commit, it takes less time to build the graph.

• I do not understand the point of this line. Could you explain? To me all it does is add a vertex v0

  G = H.union(Graph([[v0], lambda x, y: x != y])) # to make sure vertices are not relabeled
  

Nathann

[dimpase]

New commits:

​9510c70

trac #19098: Speedup

[git]

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

​4fd56a1

use TaylorTwographSRG in taylor_twograph

[dimpase]

Replying to ncohen:

Helloooooooooo Dima,

Two questions about this branch:

• It seems that you do not use the taylor_twograph function anywhere. If you think that it is useful in its own right I do not mind, but I couldn't help but notice the apparently large overlap between the code of taylor_twograph and the code of TaylorTwographDescendantSRG. Couldn't you let one of the two functions call the other? Especially since with the speedup commit, it takes less time to build the graph.

OK, see my last commit.

• I do not understand the point of this line. Could you explain? To me all it does is add a vertex v0

  G = H.union(Graph([[v0], lambda x, y: x != y])) # to make sure vertices are not relabeled
  

it makes Graph([v0]) have vertex named by what's in v0 rather than just by number 0. And so G's vertex names stay uniform. Perhaps there is a less ugly way, I don't know.

---

New commits:

​4fd56a1

use TaylorTwographSRG in taylor_twograph

[ncohen]

it makes Graph([v0]) have vertex named by what's in v0 rather than just by number 0.

What about your_graph.add_vertex(v0)?

[git]

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

​83f94e4

just add vertex v0

[dimpase]

Replying to ncohen:

it makes Graph([v0]) have vertex named by what's in v0 rather than just by number 0.

What about your_graph.add_vertex(v0)?

done by the last commit, thanks!

[ncohen]

Hellooooooooo,

• Could you add an INPUT: section for every function that takes arguments as input?

• It is not necessary to check in taylor_twograph that q is an odd prime power, as this is done by the call to the subfunction

• Why?

  -        sage: G = SRG_253_140_87_65()                # optional - gap_packages
  -        sage: G.is_strongly_regular(parameters=True) # optional - gap_packages
  +        sage: G = SRG_253_140_87_65()
  +        sage: G.is_strongly_regular(parameters=True)
  

• (Unrelated) turns out that we have another problem with names

  sage: graphs.strongly_regular_graph(126,50,13,24)
  Subgraph of (Distance graph for distance 2 in ): Graph on 126 vertices
  

Nathann

[git]

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

​6c0c890	trac #19133: Merged with 6.9.beta5
​3bc31a1	trac #19133: Broken doctests
​ffcf6ac	Merge remote-tracking branch 'trac/public/19133' into tay2
​2159763	fix a docstring typo in #19133

[dimpase]

Replying to ncohen:

• Why?

  -        sage: G = SRG_253_140_87_65()                # optional - gap_packages
  -        sage: G.is_strongly_regular(parameters=True) # optional - gap_packages
  +        sage: G = SRG_253_140_87_65()
  +        sage: G.is_strongly_regular(parameters=True)
  

oops, I forgot to merge later updates to #19133. Fixed in the last push, as well as fixed a further trivial typo in #19133.

• (Unrelated) turns out that we have another problem with names

  sage: graphs.strongly_regular_graph(126,50,13,24)
  Subgraph of (Distance graph for distance 2 in ): Graph on 126 vertices
  

IMHO all these SRG_... functions ought to return proper graph names. not on this ticket...

[git]

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

​6253d7a

added INPUT, removed unnecessary check

[dimpase]

Replying to git:

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

​6253d7a

added INPUT, removed unnecessary check

this should address the rest of comment 43.

[ncohen]

Okayyyyyyyyyyyyyyyyyyyyyyyyyyy !!

Thanks,

Nathann