Opened 3 years ago

Closed 3 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) Commit: 8b899aba92ab5fbb66ca0901fd1d065233cda96c
Dependencies: #18948, #18934 Stopgaps:

Description (last modified by ncohen)

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 3 years ago by ncohen

  • Branch set to u/ncohen/18960
  • Status changed from new to needs_review

comment:2 Changed 3 years ago by git

  • Commit set to 6390dd942ab5c913d08ba183c84be76a876baf93

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

a0173e2trac #18948: Strongly Regular Graphs database
4adcf95trac #18948: Two missing graphs
cf50d70trac #18948: Merged with 6.8
6390dd9trac #18960: Strongly Regular Graphs from two-weight codes

comment:3 Changed 3 years ago by dlucas

  • Cc dlucas added

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

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 3 years ago by dimpase

wrong ticket, sorry, should have been #18948...

Last edited 3 years ago by dimpase (previous) (diff)

comment:6 Changed 3 years ago by dimpase

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: Changed 3 years ago by 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

Nathann

comment:8 Changed 3 years ago by git

  • Commit changed from 6390dd942ab5c913d08ba183c84be76a876baf93 to f688421345a78e5ad26914a702ca9408b2a9725c

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

bad9715Hid encoders under codes.encoders.<tab>
3715880Fix related to encoders_catalog file
f447b9aUpdated documentation in encoder
e8f9fdbMerge with 6.8beta3
188b56fMinor changes
d94c53aUpdate to 6.8
aa42238Integrated reviewer's comments
17a229etrac #18376: Merged with 6.9.beta0
3596836trac #18960: Merged with 6.9.beta0
f688421trac #18960: Adding nonzero somewhere

comment:9 Changed 3 years ago by git

  • Commit changed from f688421345a78e5ad26914a702ca9408b2a9725c to 606d15fbf46b427ed47a92e7250d75f4711cdd78

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

3eee1e7trac #18960: Merge 6.9.beta0
606d15ftrac #18960: Adding nonzero somewhere

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

comment:11 in reply to: ↑ 10 Changed 3 years ago by dimpase

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: Changed 3 years ago by ncohen

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 3 years ago by dimpase

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 3 years ago by git

  • Commit changed from 606d15fbf46b427ed47a92e7250d75f4711cdd78 to 83ed332c58dbad71fe5b74d8c2d9e3aa3fe52d84

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

83ed332trac #18960: Again...

comment:15 Changed 3 years ago by dimpase

Could you please change [LintSchrijver81] to [vLintSchrijver81] to indicate that it's van Lint?

comment:16 follow-up: Changed 3 years ago by dimpase

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 3 years ago by ncohen

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 3 years ago by git

  • Commit changed from 83ed332c58dbad71fe5b74d8c2d9e3aa3fe52d84 to dc2d3261a823a5ed8db1129497ada25e3059d7ee

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

dc2d326trac #18960: Lint -> vLint

comment:19 Changed 3 years ago by ncohen

  • Description modified (diff)

comment:20 Changed 3 years ago by dimpase

  • Status changed from needs_review to positive_review

LGTM

comment:21 Changed 3 years ago by ncohen

Thanks !!!!

comment:22 follow-up: Changed 3 years ago by dimpase

don't you need to rebase it over #18948 ?

comment:23 Changed 3 years ago by git

  • 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:

8f25493trac #18948: Merged with 6.9.beta0
a9280c9trac #18948: Rephrasing the doc
cf8f2datrac #18948: guess mu
4f51703trac #18948: DOcstring
a75774ftrac #18948: take into account the BIBD from #18934
6071efctrac #18960: Merge with updated #18948

comment:24 in reply to: ↑ 22 Changed 3 years ago by ncohen

  • Status changed from needs_review to positive_review

don't you need to rebase it over #18948 ?

Done.

Nathann

comment:25 Changed 3 years ago by dimpase

  • Reviewers set to Dima Pasechnik

comment:26 Changed 3 years ago by git

  • 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:

a0cac66trac #18934: new BIBD: (91,7,1), (66,6,1), (76,6,1), (96,6,1)
e46b058trac #18934: New (v,6,1)-BIBD with v=201
a04a2fbtrac #18934: Broken doctests
11e9f1ftrac #18934: Last one -> (126,6,1)-BIBD
796bcdetrac #18934: Merged with 6.8.rc1
6ed1abftrac #18934: Fixed credits
62ce12ctrac #18934: Merged with beta0
f4f5566trac #18948: Merge with updated #18934
d1d25a0trac #18948: Broken doctest
8b899abtrac #18960: Merged with updated #18948

comment:27 Changed 3 years ago by ncohen

  • Dependencies changed from #18948 to #18948, #18934
  • Status changed from needs_review to positive_review

comment:28 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/18960 to 8b899aba92ab5fbb66ca0901fd1d065233cda96c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.