Opened 5 years ago
Closed 5 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 5 years ago by
comment:2 Changed 5 years ago by
- Cc ncohen added
comment:3 Changed 5 years ago by
- Branch set to u/dimpase/taylor2graphs
- Commit set to ef096b5f3c3c4eeb745cf3e27f5e66094b08550d
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
|
comment:4 Changed 5 years ago by
- Dependencies set to #18972, #18997
comment:5 Changed 5 years ago by
- Commit changed from ef096b5f3c3c4eeb745cf3e27f5e66094b08550d to 52b555929e8511cf761972559ded1e6064863bd1
comment:6 Changed 5 years ago by
- Dependencies changed from #18972, #18997 to #18972, #18997, #19099
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
|
comment:7 Changed 5 years ago by
- Commit changed from 52b555929e8511cf761972559ded1e6064863bd1 to 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6
comment:8 Changed 5 years ago by
- Commit changed from 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6 to 773d10d2b417f72829fcf0556f2426bd02cd0efb
Branch pushed to git repo; I updated commit sha1. New commits:
773d10d | more doctests and docs and typos fixed
|
comment:9 follow-up: ↓ 10 Changed 5 years ago by
- 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: ↓ 12 Changed 5 years ago by
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 5 years ago by
- Status changed from needs_review to needs_work
doc does not build, see patchbot report
comment:12 in reply to: ↑ 10 Changed 5 years ago by
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 5 years ago by
- Commit changed from 773d10d2b417f72829fcf0556f2426bd02cd0efb to bc401cef4985f4dff03d932786f33aeb574528df
Branch pushed to git repo; I updated commit sha1. New commits:
bc401ce | satisfied sphinx (bug shows only after make doc-clean)
|
comment:14 Changed 5 years ago by
- Status changed from needs_work to needs_review
comment:15 follow-up: ↓ 16 Changed 5 years ago by
What is this ? O_o
+- cf. ``git blame`` for the others involved
Nathann
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 18 Changed 5 years ago by
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 5 years ago by
of course I can remove it if you like...
comment:18 in reply to: ↑ 16 ; follow-up: ↓ 20 Changed 5 years ago by
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 5 years ago by
- Commit changed from bc401cef4985f4dff03d932786f33aeb574528df to 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa
Branch pushed to git repo; I updated commit sha1. New commits:
86495a4 | authors cleared
|
comment:20 in reply to: ↑ 18 Changed 5 years ago by
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: ↓ 26 Changed 5 years ago by
- Commit changed from 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa to edb886e9f9d0f505f272fe769e69e8a51ab265df
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
edb886e | authors cleared
|
comment:22 Changed 5 years ago by
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: ↓ 25 Changed 5 years ago by
+ 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 5 years ago by
- Commit changed from edb886e9f9d0f505f272fe769e69e8a51ab265df to 6262d658ffd644af0146835a081d1abc9241a711
Branch pushed to git repo; I updated commit sha1. New commits:
6262d65 | give the right references, and also the typo missed earlier
|
comment:25 in reply to: ↑ 23 Changed 5 years ago by
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 5 years ago by
comment:27 Changed 5 years ago by
comment:28 Changed 5 years ago by
- Commit changed from 6262d658ffd644af0146835a081d1abc9241a711 to 685d86df4c9257a64f4c23501a1c97bd9af59d40
Branch pushed to git repo; I updated commit sha1. New commits:
685d86d | utf-8...
|
comment:29 Changed 5 years ago by
- Commit changed from 685d86df4c9257a64f4c23501a1c97bd9af59d40 to dbca37ec255b521ee12662d915a492f55261b842
Branch pushed to git repo; I updated commit sha1. New commits:
dbca37e | a sporadic example related to 2-graphs
|
comment:30 Changed 5 years ago by
- Commit changed from dbca37ec255b521ee12662d915a492f55261b842 to 6a6f7b3abad0ee5ea82166f79c52e25793775bfd
comment:31 Changed 5 years ago by
- Dependencies changed from #18972, #18997, #19099 to #18972, #18997, #19099, #19133
comment:32 Changed 5 years ago by
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: ↓ 34 Changed 5 years ago by
- Commit changed from 6a6f7b3abad0ee5ea82166f79c52e25793775bfd to d7878be6695b3386b8e5e10ed71634b08519db7d
Branch pushed to git repo; I updated commit sha1. New commits:
d7878be | Merge branch 'taylor2graphs' into tay2
|
comment:34 in reply to: ↑ 33 Changed 5 years ago by
comment:35 Changed 5 years ago by
I pushed a speedup at public/19098
.
Nathann
comment:36 follow-up: ↓ 39 Changed 5 years ago by
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 oftaylor_twograph
and the code ofTaylorTwographDescendantSRG
. 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 5 years ago by
- Branch changed from u/dimpase/taylor2graphs to public/19098
- Commit changed from d7878be6695b3386b8e5e10ed71634b08519db7d to 9510c7015c4252b82d60b55d80c47ccd1b6d15f4
New commits:
9510c70 | trac #19098: Speedup
|
comment:38 Changed 5 years ago by
- Commit changed from 9510c7015c4252b82d60b55d80c47ccd1b6d15f4 to 4fd56a1f10901663ea001460dd2dfe0da666f4c8
Branch pushed to git repo; I updated commit sha1. New commits:
4fd56a1 | use TaylorTwographSRG in taylor_twograph
|
comment:39 in reply to: ↑ 36 ; follow-up: ↓ 40 Changed 5 years ago by
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 oftaylor_twograph
and the code ofTaylorTwographDescendantSRG
. 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
|
comment:40 in reply to: ↑ 39 ; follow-up: ↓ 42 Changed 5 years ago by
it makes
Graph([v0])
have vertex named by what's inv0
rather than just by number 0.
What about your_graph.add_vertex(v0)
?
comment:41 Changed 5 years ago by
- Commit changed from 4fd56a1f10901663ea001460dd2dfe0da666f4c8 to 83f94e41f1fc8647e105fbf956bea44426e30d5f
Branch pushed to git repo; I updated commit sha1. New commits:
83f94e4 | just add vertex v0
|
comment:42 in reply to: ↑ 40 Changed 5 years ago by
Replying to ncohen:
it makes
Graph([v0])
have vertex named by what's inv0
rather than just by number 0.What about
your_graph.add_vertex(v0)
?
done by the last commit, thanks!
comment:43 follow-up: ↓ 45 Changed 5 years ago by
Hellooooooooo,
- Could you add an INPUT: section for every function that takes arguments as input?
- It is not necessary to check in
taylor_twograph
thatq
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 5 years ago by
- Commit changed from 83f94e41f1fc8647e105fbf956bea44426e30d5f to 21597637cb5c8a4aa781a1be3dae88375a58979b
comment:45 in reply to: ↑ 43 Changed 5 years ago by
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: ↓ 47 Changed 5 years ago by
- Commit changed from 21597637cb5c8a4aa781a1be3dae88375a58979b to 6253d7ad6618213d1f32bd818592b5e7b83ef467
Branch pushed to git repo; I updated commit sha1. New commits:
6253d7a | added INPUT, removed unnecessary check
|
comment:47 in reply to: ↑ 46 Changed 5 years ago by
comment:48 Changed 5 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
Okayyyyyyyyyyyyyyyyyyyyyyyyyyy !!
Thanks,
Nathann
comment:49 Changed 5 years ago by
- Branch changed from public/19098 to 6253d7ad6618213d1f32bd818592b5e7b83ef467
- Resolution set to fixed
- Status changed from positive_review to closed
also improve
__init__
ofTwoGraph
, using**kwds
.