Opened 6 years ago
Closed 6 years ago
#18960 closed enhancement (fixed)
Strongly Regular Graphs from twoweight codes
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  dimpase, dlucas  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  8b899ab (Commits, GitHub, GitLab)  Commit:  8b899aba92ab5fbb66ca0901fd1d065233cda96c 
Dependencies:  #18948, #18934  Stopgaps: 
Description (last modified by )
This ticket adds several constructions of strongly regular graphs from twoweight codes.
The data used here has been provided by Eric Chen, using information available on his database of twoweight codes: http://moodle.tec.hkr.se/~chen/research/2weightcodes/search.php
Nathann
Change History (28)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/18960
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 6390dd942ab5c913d08ba183c84be76a876baf93
comment:3 Changed 6 years ago by
 Cc dlucas added
comment:4 followup: ↓ 5 Changed 6 years ago by
Test if a Paley graph is `(v,k,\lambda,\mu)`strongly regular.
Huh? Do you mean
Test whether a `(v,k,\lambda,\mu)`strongly regular graph is Paley.
comment:5 in reply to: ↑ 4 Changed 6 years ago by
wrong ticket, sorry, should have been #18948...
comment:6 Changed 6 years ago by
It is said to be *projective* if any two of its codewords are linearly independent.
This needs an extra care: a projective code, if defined this way, cannot contain the all0 word.
(Usually a projective code is defined as a subset of points in a projective space; your definition is OK, if you add that it does not contain an all0 word).
comment:7 followup: ↓ 10 Changed 6 years ago by
Hmmmm... Too bad you did not review van Lint and Schrijver's paper, for this is a copy paste of definition 2 (page 2) of their paper :P
http://link.springer.com/article/10.1007%2FBF02579178#page1
Nathann
comment:8 Changed 6 years ago by
 Commit changed from 6390dd942ab5c913d08ba183c84be76a876baf93 to f688421345a78e5ad26914a702ca9408b2a9725c
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
bad9715  Hid encoders under codes.encoders.<tab>

3715880  Fix related to encoders_catalog file

f447b9a  Updated documentation in encoder

e8f9fdb  Merge with 6.8beta3

188b56f  Minor changes

d94c53a  Update to 6.8

aa42238  Integrated reviewer's comments

17a229e  trac #18376: Merged with 6.9.beta0

3596836  trac #18960: Merged with 6.9.beta0

f688421  trac #18960: Adding nonzero somewhere

comment:9 Changed 6 years ago by
 Commit changed from f688421345a78e5ad26914a702ca9408b2a9725c to 606d15fbf46b427ed47a92e7250d75f4711cdd78
comment:10 in reply to: ↑ 7 ; followup: ↓ 11 Changed 6 years ago by
Replying to ncohen:
Hmmmm... Too bad you did not review van Lint and Schrijver's paper, for this is a copy paste of definition 2 (page 2) of their paper
:P
http://link.springer.com/article/10.1007%2FBF02579178#page1
well, it's behind a paywall for me (and Oxford  although we should have a paper copy) Anyhow, your correction does not go far enough: namely, a projective code cannot have all0 codeword, in all the (free) internet sources I can find.
comment:11 in reply to: ↑ 10 Changed 6 years ago by
Replying to dimpase:
Replying to ncohen:
Hmmmm... Too bad you did not review van Lint and Schrijver's paper, for this is a copy paste of definition 2 (page 2) of their paper
:P
http://link.springer.com/article/10.1007%2FBF02579178#page1
well, it's behind a paywall for me (and Oxford  although we should have a paper copy) Anyhow, your correction does not go far enough: namely, a projective code cannot have all0 codeword, in all the (free) internet sources I can find.
Oh, I see  they belong to a school allowing all0 vector while talking about linear dependence. Then what you had before is OK. Well, almost OK, because a code consisting of just one word, all0, would be projective by their definition, but it won't for any other definition.
comment:12 followup: ↓ 13 Changed 6 years ago by
Are you okay with the current state? I do not think that much confusion can happen anymore, in its current form.
Nathann
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Replying to ncohen:
Are you okay with the current state? I do not think that much confusion can happen anymore, in its current form.
No, check the definition! It is about linear independence of coordinates, not codewords. The definition, with details, is actually from Delsarte's [4], where you see what coordinates are; [4] is a free download. In a nutshell, take the matrix M with the rows consisting of the codewords of C (it suffices to take any generating subset set of codewords, if we talk about linear codes). Then the definition says that every two columns of M are linearly independent.
Equivalently, they add, the dual code C* of C has minimal distance 3: indeed, a linear dependence between two columns of M gives rise to a weight 2 word w in C*, and thus the minimal distance at most 2 (take the distance between all0 word in C* and w).
Sorry for the confusion; this is indeed about a set of points in a projective space, the space of columns of Mbut not the set of codewords of C...
comment:14 Changed 6 years ago by
 Commit changed from 606d15fbf46b427ed47a92e7250d75f4711cdd78 to 83ed332c58dbad71fe5b74d8c2d9e3aa3fe52d84
Branch pushed to git repo; I updated commit sha1. New commits:
83ed332  trac #18960: Again...

comment:15 Changed 6 years ago by
Could you please change [LintSchrijver81] to [vLintSchrijver81] to indicate that it's van Lint?
comment:16 followup: ↓ 17 Changed 6 years ago by
I'm a bit confused about how one is supposed to find strongly_regular_from_two_weight_code
in Sage. It's not exported, and for some reason doesn't pop up in the documentation index...
comment:17 in reply to: ↑ 16 Changed 6 years ago by
Could you please change [LintSchrijver81] to [vLintSchrijver81] to indicate that it's van Lint?
Done. I don't know if that is the whole of your review, but it would be cool if you could review everything and give your comments afterwards. Otherwise I have to make individual commits for oneletter changes, and well...
I'm a bit confused about how one is supposed to find
strongly_regular_from_two_weight_code
in Sage. It's not exported, and for some reason doesn't pop up in the documentation index...
It appears in the documentation of strongly_regular_db
when I build it. If it does not appear on your computer then there is a problem. About your "how to find it": not all graph methods appear in the Graph
class. Some, which I consider more 'confidential', have to be imported from the modules. Like several kind of weird vertex/edge colorings.
Nathann
comment:18 Changed 6 years ago by
 Commit changed from 83ed332c58dbad71fe5b74d8c2d9e3aa3fe52d84 to dc2d3261a823a5ed8db1129497ada25e3059d7ee
Branch pushed to git repo; I updated commit sha1. New commits:
dc2d326  trac #18960: Lint > vLint

comment:19 Changed 6 years ago by
 Description modified (diff)
comment:21 Changed 6 years ago by
Thanks !!!!
comment:22 followup: ↓ 24 Changed 6 years ago by
don't you need to rebase it over #18948 ?
comment:23 Changed 6 years ago by
 Commit changed from dc2d3261a823a5ed8db1129497ada25e3059d7ee to 6071efc6d9af83a7d397e2ca54a63d6d401df06e
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
8f25493  trac #18948: Merged with 6.9.beta0

a9280c9  trac #18948: Rephrasing the doc

cf8f2da  trac #18948: guess mu

4f51703  trac #18948: DOcstring

a75774f  trac #18948: take into account the BIBD from #18934

6071efc  trac #18960: Merge with updated #18948

comment:24 in reply to: ↑ 22 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:25 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
comment:26 Changed 6 years ago by
 Commit changed from 6071efc6d9af83a7d397e2ca54a63d6d401df06e to 8b899aba92ab5fbb66ca0901fd1d065233cda96c
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
a0cac66  trac #18934: new BIBD: (91,7,1), (66,6,1), (76,6,1), (96,6,1)

e46b058  trac #18934: New (v,6,1)BIBD with v=201

a04a2fb  trac #18934: Broken doctests

11e9f1f  trac #18934: Last one > (126,6,1)BIBD

796bcde  trac #18934: Merged with 6.8.rc1

6ed1abf  trac #18934: Fixed credits

62ce12c  trac #18934: Merged with beta0

f4f5566  trac #18948: Merge with updated #18934

d1d25a0  trac #18948: Broken doctest

8b899ab  trac #18960: Merged with updated #18948

comment:27 Changed 6 years ago by
 Dependencies changed from #18948 to #18948, #18934
 Status changed from needs_review to positive_review
comment:28 Changed 6 years ago by
 Branch changed from u/ncohen/18960 to 8b899aba92ab5fbb66ca0901fd1d065233cda96c
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #18948: Strongly Regular Graphs database
trac #18948: Two missing graphs
trac #18948: Merged with 6.8
trac #18960: Strongly Regular Graphs from twoweight codes