Strongly Regular Graphs from two-weight codes

[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

[git]

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

​a0173e2	trac #18948: Strongly Regular Graphs database
​4adcf95	trac #18948: Two missing graphs
​cf50d70	trac #18948: Merged with 6.8
​6390dd9	trac #18960: Strongly Regular Graphs from two-weight codes

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

[dimpase]

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

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

[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

[git]

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

[git]

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

​3eee1e7	trac #18960: Merge 6.9.beta0
​606d15f	trac #18960: Adding nonzero somewhere

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

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

[ncohen]

Are you okay with the current state? I do not think that much confusion can happen anymore, in its current form.

Nathann

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

[git]

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

​83ed332

trac #18960: Again...

[dimpase]

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

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

[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

[git]

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

​dc2d326

trac #18960: Lint -> vLint

[dimpase]

LGTM

[ncohen]

Thanks !!!!

[dimpase]

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

[git]

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

[ncohen]

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

Done.

Nathann

[git]

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