Opened 6 years ago
Closed 6 years ago
#18960 closed enhancement (fixed)
Strongly Regular Graphs from two-weight codes
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 two-weight codes.
The data used here has been provided by Eric Chen, using information available on his database of two-weight codes: http://moodle.tec.hkr.se/~chen/research/2-weight-codes/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 follow-up: ↓ 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 all-0 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 all-0 word).
comment:7 follow-up: ↓ 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#page-1
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 ; follow-up: ↓ 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#page-1
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 all-0 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#page-1
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 all-0 codeword, in all the (free) internet sources I can find.
Oh, I see - they belong to a school allowing all-0 vector while talking about linear dependence. Then what you had before is OK. Well, almost OK, because a code consisting of just one word, all-0, would be projective by their definition, but it won't for any other definition.
comment:12 follow-up: ↓ 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 all-0 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 M---but 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 follow-up: ↓ 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 one-letter 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 follow-up: ↓ 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 two-weight codes