Affine Polar Graphs

[nathanncohen]

Thank youuuuuuUUUUUUUUUuuuuuu Brouwer !!! :-P

Nathann

P.S. : This patch "does not really" depend on #14589, but here is what happens when calling "is_strongly_regular" on a big graph. With the patch :

sage: g
Affine Polar Graph VO^+(10,2): Graph on 1024 vertices
sage: %time g.is_strongly_regular(parameters = True)
CPU times: user 3.30 s, sys: 0.00 s, total: 3.30 s
Wall time: 3.31 s
(1024, 527, 270, 272)

Without the patch

sage: %time g.is_strongly_regular(parameters = True)
CPU times: user 316.33 s, sys: 0.08 s, total: 316.41 s
Wall time: 317.20 s
(1024, 527, 270, 272)

Annnnnd the doctests that this patch adds are a bit faster as a result :-P

Depends on #16362

CC: @dimpase @sagetrac-azi @sagetrac-Slani

Component: graph theory

Author: Nathann Cohen, Dima Pasechnik

Branch/Commit: 3ef564e

Reviewer: Nathann Cohen, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/14631

[nathanncohen]

Attachment: trac_14631.patch.gz

[dimpase]

comment:4

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours of a vertex in a polar space graph.

[nathanncohen]

comment:5

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours of a vertex in a polar space graph.

Ahahah. Dima, I have NOooooooooo idea what "normal polar space graphs" are. I barely understand what this patch does in the first place. Why don't you give it a try, by the way ?

Nathann

[dimpase]

comment:6

Replying to @nathanncohen:

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours of a vertex in a polar space graph.

Ahahah. Dima, I have NOooooooooo idea what "normal polar space graphs" are.

I sent you a link to a text about them, didn't I? Here is another link:
http://www.win.tue.nl/~aeb/graphs/srghub.html
Most of the graphs described there are of this type (expect the Grassmann graphs, E_6, and the rest of low-dimensional examples).

I barely understand what this patch does in the first place. Why don't you give it a try, by the way ?

I have about 10 other things I must work on now (if not last month or year :)), and organization of this:
http://web.spms.ntu.edu.sg/~dima/IMS2013/
And I don't even have a fixed job, as you know, so you don't feel the pressure I do feel from this side...

[nathanncohen]

comment:8

Made it a Git branch, as I need to use it.

Nathann

[nathanncohen]

Branch: u/ncohen/14631

[sagetrac-git]

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

a9faba0

trac #14631: Affine Polar Graphs

[sagetrac-git]

Commit: a9faba0

[dimpase]

comment:12

With #16362 one can construct VO(n,q,) by merely taking the subgraph induced on non-neighbours of a vertex in
OrthogonalPolarGraph(n+2,q,<sign>). I don't insist on rewriting the code, but this should at least be mentioned in the docs somewhere.

[nathanncohen]

comment:13

With #16362 one can construct VO(n,q,) by merely taking the subgraph induced on non-neighbours of a vertex in
OrthogonalPolarGraph(n+2,q,<sign>). I don't insist on rewriting the code, but this should at least be mentioned in the docs somewhere.

That's what happens when a patch stays in "needs_review" for one year.

I will add a commit in a second :-P

Nathann

[sagetrac-git]

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

a1ec9b5	trac #14631: Merged with 6.3.beta1
6adc14b	trac #16362: Polar Graph
f1e4fb3	just a small pep8 cleanup
e3c4aaa	trac #16362: Reviewer's comments
0089d6c	trac #16362: Broken documentation
c5cc1d9	trac #14631: Merged with #16362
e725be9	trac #14631: Note added

[sagetrac-git]

Changed commit from a9faba0 to e725be9

[dimpase]

comment:15

well, my comment on this fact is about a year old :–)

---

New commits:

a1ec9b5	trac #14631: Merged with 6.3.beta1
6adc14b	trac #16362: Polar Graph
f1e4fb3	just a small pep8 cleanup
e3c4aaa	trac #16362: Reviewer's comments
0089d6c	trac #16362: Broken documentation
c5cc1d9	trac #14631: Merged with #16362
e725be9	trac #14631: Note added

[nathanncohen]

comment:16

I don't get a word of what you said in this comment.

Nathann

[dimpase]

comment:17

Replying to @nathanncohen:

I don't get a word of what you said in this comment.

It must be then pure coincidence that I mention http://www.win.tue.nl/~aeb/graphs/srghub.html there (the link mentioned by you in #16362) :P

[dimpase]

comment:18

Affine Polar Graph page should be
Affine Polar Graphs page

[dimpase]

comment:19

This code has the same potential bug as mentioned in here.
Please fix.

[dimpase]

comment:20

Also, for consistency with #16362, the function AffinePolarGraph should be renamed AffineOrthogonalPolarGraph.

[nathanncohen]

Changed dependencies from #14589 to #16362

[nathanncohen]

comment:21

Done.

[sagetrac-git]

Changed commit from e725be9 to 4f82fa5

[sagetrac-git]

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

257082d	trac #14631: Reviewer's comments
272e18f	trac #16362: Broken doc 2
4f82fa5	trac #14631: Merged with #16362

[dimpase]

Changed branch from u/ncohen/14631 to u/dimpase/14631

[dimpase]

Changed commit from 4f82fa5 to 3ef564e

[dimpase]

comment:24

if you're happy with my changes please set this to positive review!

---

New commits:

3ef564e

libGAPification

[nathanncohen]

comment:25

Well, given that it still passes tests... :-)

Nathann

[nathanncohen]

Reviewer: Nathann Cohen, Dima Pasechnik

[vbraun]

Changed branch from u/dimpase/14631 to 3ef564e