Opened 4 years ago

Closed 4 years ago

#19098 closed enhancement (fixed)

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

Reported by: dimpase Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: ncohen Merged in:
Authors: Dima Pasechnik Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 6253d7a (Commits) Commit: 6253d7ad6618213d1f32bd818592b5e7b83ef467
Dependencies: #18972, #18997, #19099, #19133 Stopgaps:

Description

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"

Change History (49)

comment:1 Changed 4 years ago by dimpase

also improve __init__ of TwoGraph, using **kwds.

comment:2 Changed 4 years ago by ncohen

  • Cc ncohen added

comment:3 Changed 4 years ago by dimpase

  • Branch set to u/dimpase/taylor2graphs
  • Commit set to ef096b5f3c3c4eeb745cf3e27f5e66094b08550d

Last 10 new commits:

ab18d25merge Merge branch 'unitary' into the latest #18972
5450f1edoctest fixes from John Palmieri: Thanks John! They help!
50a6efcMerge branch 'seidelsw' into unitary
35a9b17doctest fixes
fd9a689Merge branch 'seidelsw' into unitary
acc985aaddressed reviewer's points
ee9c5d6address #18997:24
88ed777Merge branch 'develop' into unitary
ce952f9Merge branch 'unitary' into taylor2graphs
ef096b5implement the constructions of SRGs on q^3 and q^3+1 points

comment:4 Changed 4 years ago by dimpase

  • Dependencies set to #18972, #18997

comment:5 Changed 4 years ago by git

  • Commit changed from ef096b5f3c3c4eeb745cf3e27f5e66094b08550d to 52b555929e8511cf761972559ded1e6064863bd1

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

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

comment:6 Changed 4 years ago by dimpase

  • Dependencies changed from #18972, #18997 to #18972, #18997, #19099

New commits:

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

New commits:

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

comment:7 Changed 4 years ago by git

  • Commit changed from 52b555929e8511cf761972559ded1e6064863bd1 to 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6

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

1cf1066replace duplicate [vLintBrouwer84] with [BvL84]
9758eb6recongintion of Taylor 2-graph srg. 6 more graphs in!

comment:8 Changed 4 years ago by git

  • Commit changed from 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6 to 773d10d2b417f72829fcf0556f2426bd02cd0efb

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

773d10dmore doctests and docs and typos fixed

comment:9 follow-up: Changed 4 years ago by dimpase

  • Status changed from new to needs_review

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by 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?

comment:11 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

doc does not build, see patchbot report

comment:12 in reply to: ↑ 10 Changed 4 years ago by 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()
...

comment:13 Changed 4 years ago by git

  • Commit changed from 773d10d2b417f72829fcf0556f2426bd02cd0efb to bc401cef4985f4dff03d932786f33aeb574528df

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

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

comment:14 Changed 4 years ago by dimpase

  • Status changed from needs_work to needs_review

comment:15 follow-up: Changed 4 years ago by ncohen

What is this ? O_o

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

Nathann

comment:16 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by 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?

comment:17 Changed 4 years ago by dimpase

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

comment:18 in reply to: ↑ 16 ; follow-up: Changed 4 years ago by 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

comment:19 Changed 4 years ago by git

  • Commit changed from bc401cef4985f4dff03d932786f33aeb574528df to 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa

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

86495a4authors cleared

comment:20 in reply to: ↑ 18 Changed 4 years ago by 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.

comment:21 follow-up: Changed 4 years ago by git

  • Commit changed from 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa to edb886e9f9d0f505f272fe769e69e8a51ab265df

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

edb886eauthors cleared

comment:22 Changed 4 years ago by 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

comment:23 follow-up: Changed 4 years ago by 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

comment:24 Changed 4 years ago by git

  • Commit changed from edb886e9f9d0f505f272fe769e69e8a51ab265df to 6262d658ffd644af0146835a081d1abc9241a711

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

6262d65give the right references, and also the typo missed earlier

comment:25 in reply to: ↑ 23 Changed 4 years ago by 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.

comment:26 in reply to: ↑ 21 Changed 4 years ago by dimpase

Replying to git:

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

edb886eauthors cleared

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

comment:27 Changed 4 years ago by dimpase

  • Authors set to Dima Pasechnik

comment:28 Changed 4 years ago by git

  • Commit changed from 6262d658ffd644af0146835a081d1abc9241a711 to 685d86df4c9257a64f4c23501a1c97bd9af59d40

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

685d86dutf-8...

comment:29 Changed 4 years ago by git

  • Commit changed from 685d86df4c9257a64f4c23501a1c97bd9af59d40 to dbca37ec255b521ee12662d915a492f55261b842

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

dbca37ea sporadic example related to 2-graphs

comment:30 Changed 4 years ago by git

  • Commit changed from dbca37ec255b521ee12662d915a492f55261b842 to 6a6f7b3abad0ee5ea82166f79c52e25793775bfd

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

302e6bctrac #19133: Three Witt-based strongly regular graphs
6a6f7b3Merge remote-tracking branch 'trac/public/19133' into taylor2graphs

comment:31 Changed 4 years ago by dimpase

  • Dependencies changed from #18972, #18997, #19099 to #18972, #18997, #19099, #19133

comment:32 Changed 4 years ago by 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

comment:33 follow-up: Changed 4 years ago by git

  • Commit changed from 6a6f7b3abad0ee5ea82166f79c52e25793775bfd to d7878be6695b3386b8e5e10ed71634b08519db7d

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

d7878beMerge branch 'taylor2graphs' into tay2

comment:34 in reply to: ↑ 33 Changed 4 years ago by dimpase

Replying to git:

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

d7878beMerge branch 'taylor2graphs' into tay2

rebased over the latest beta

comment:35 Changed 4 years ago by ncohen

I pushed a speedup at public/19098.

Nathann

comment:36 follow-up: Changed 4 years ago by 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

comment:37 Changed 4 years ago by dimpase

  • Branch changed from u/dimpase/taylor2graphs to public/19098
  • Commit changed from d7878be6695b3386b8e5e10ed71634b08519db7d to 9510c7015c4252b82d60b55d80c47ccd1b6d15f4

New commits:

9510c70trac #19098: Speedup

comment:38 Changed 4 years ago by git

  • Commit changed from 9510c7015c4252b82d60b55d80c47ccd1b6d15f4 to 4fd56a1f10901663ea001460dd2dfe0da666f4c8

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

4fd56a1use TaylorTwographSRG in taylor_twograph

comment:39 in reply to: ↑ 36 ; follow-up: Changed 4 years ago by 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:

4fd56a1use TaylorTwographSRG in taylor_twograph

comment:40 in reply to: ↑ 39 ; follow-up: Changed 4 years ago by 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)?

comment:41 Changed 4 years ago by git

  • Commit changed from 4fd56a1f10901663ea001460dd2dfe0da666f4c8 to 83f94e41f1fc8647e105fbf956bea44426e30d5f

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

83f94e4just add vertex v0

comment:42 in reply to: ↑ 40 Changed 4 years ago by 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!

comment:43 follow-up: Changed 4 years ago by 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

comment:44 Changed 4 years ago by git

  • Commit changed from 83f94e41f1fc8647e105fbf956bea44426e30d5f to 21597637cb5c8a4aa781a1be3dae88375a58979b

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

6c0c890trac #19133: Merged with 6.9.beta5
3bc31a1trac #19133: Broken doctests
ffcf6acMerge remote-tracking branch 'trac/public/19133' into tay2
2159763fix a docstring typo in #19133

comment:45 in reply to: ↑ 43 Changed 4 years ago by 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...

comment:46 follow-up: Changed 4 years ago by git

  • Commit changed from 21597637cb5c8a4aa781a1be3dae88375a58979b to 6253d7ad6618213d1f32bd818592b5e7b83ef467

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

6253d7aadded INPUT, removed unnecessary check

comment:47 in reply to: ↑ 46 Changed 4 years ago by dimpase

Replying to git:

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

6253d7aadded INPUT, removed unnecessary check

this should address the rest of comment 43.

comment:48 Changed 4 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Okayyyyyyyyyyyyyyyyyyyyyyyyyyy !!

Thanks,

Nathann

comment:49 Changed 4 years ago by vbraun

  • Branch changed from public/19098 to 6253d7ad6618213d1f32bd818592b5e7b83ef467
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.