IncidenceStructure.is_generalized_quadrangle

[ncohen]

Simple implementation. Perhaps not very optimized, but working. Until we need something more efficient.

Nathann

[git]

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

​5fbd6a3	trac #19227: Cremona-Richmond configuration
​d0fbdf1	trac #19279: IncidenceStructure.is_generalized_quadrangle

[git]

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

​28d6c6e	trac #19227: Cremona-Richmond configuration
​4f8a84b	trac #19279: IncidenceStructure.is_generalized_quadrangle

[dimpase]

1) GQs don't necessary admit parameters; e.g.

o----o----o
|    |    |
o----o----o

is a GQ with 6 points and 5 lines, of which 2 are of size 3, and 3 of size 2. (or you can take the dual, and get 5 points and 6 lines, all lines of the same size, 2, but points incident to different number of lines). Admittedly this is a somewhat degenerate case, where either all lines have size 2, or all points are incident to exactly 2 lines; otherwise one indeed has uniformity.

2) the incidence graph is bipartite, and thus must have even girth (equal to 8, to get a GQ).

[ncohen]

1) GQs don't necessary admit parameters; e.g.

I implemented the definition from Wikipedia: ​https://en.wikipedia.org/wiki/Generalized_quadrangle

Is it wrong?

2) the incidence graph is bipartite, and thus must have even girth (equal to 8, to get a GQ).

Soooooooooo you want me to change something in my code/doc, arguing that it would make absolutely no difference because both are correct? :-P

Nathann

[dimpase]

Replying to ncohen:

1) GQs don't necessary admit parameters; e.g.

I implemented the definition from Wikipedia: ​https://en.wikipedia.org/wiki/Generalized_quadrangle

Is it wrong?

it is a definition that is unnecessarily restrictive, and actually contradicts with what wikipedia defines as a polar space. Saying that a GQ is a polar space (and it is saying it) in wikipedia sense will disallow t=1 or s=1.

2) the incidence graph is bipartite, and thus must have even girth (equal to 8, to get a GQ).

Soooooooooo you want me to change something in my code/doc, arguing that it would make absolutely no difference because both are correct? `:-)

well, in a comment in the code you say that the girth must be at least 7; but you never ever get 7 or any odd number...

[dimpase]

here is another point of view: ​http://www.win.tue.nl/~aeb/2WF02/genq.pdf if my authority is not enough (I only published a dozen papers dealing with GQs :-)).

what in wikipedia is called GQ is called regular GQ in some other sources. They are also called GQs admitting parameters...

[ncohen]

Okay. Looks like I had the right intuition in implementing it with a girth call when reading the wikipedia definition :-P

How would you want to see the code, then? Just a function that returns true/false, and the users can obtain the s/t by themselves through a call to is_regular/is_uniform?

Nathann

[dimpase]

Replying to ncohen:

Okay. Looks like I had the right intuition in implementing it with a girth call when reading the wikipedia definition :-P

How would you want to see the code, then? Just a function that returns true/false, and the users can obtain the s/t by themselves through a call to is_regular/is_uniform?

perhaps it can get a boolean parameter parameters, and, when it is True, return in addition the tuple (s,t), where one or both entries may be None?

[git]

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

​c26038e

trac #19279: Different definition

[ncohen]

Done. Could you update the wikipedia definition?

Nathann

[dimpase]

Replying to ncohen:

Done. Could you update the wikipedia definition?

this is not so easy, even if one does not mess with polar spaces...

There several streams to cover for GQs; in addition to already mentioned, there is a stream where GQs without a restriction on s,t are called weak GQs, see e.g. ​http://link.springer.com/book/10.1007/978-3-0348-0271-0

And I meanwhile have 5 overdue referee reports to write :-)

[ncohen]

Okay Dima, first you tell me that the Wikipedia definition is incorrect and ask me to implement another, and then you tell me that Wikipedia's definition is not so incorrect after all.

So let's do that: either you can give me a textbook which uses the definition that you want so that I can link to it, otherwise I will implement Wikipedia's definition which happens to coincide with "Finite Generalized Triangles" [1]

Nathann

[1] ​http://cage.ugent.be/~bamberg/FGQ.pdf

[dimpase]

I am telling you that Wikipedia definition has inconsistencies. E.g. it says that by definition a GQ is a polar space of rank 2, and on the link to polar spaces is does not give you a definition of polar space of rank 2. As well I am telling you that Wikipedia definition is by far not the only one common in the literature.

E.g., page 200 of [BCN] says: More generally, a generalized n-gon is a partial linear space (P,E) with the property that the incidence graph has diameter n and any two vertices x,y at distance i < n have c_j(x,y) = 1. It is said to be of order (s,t) if all of its lines have size s + 1 and all of its points are incident to exactly t + 1 lines.

[BCN]: ​https://drive.google.com/file/d/0B92yb82dH00zZWFJdkNsQm5nZmM/view?usp=sharing Indeed, in Ghent they might burn you at stake if you try to insist on this definition, but they have been trying to monopolise this industry for years :-)

[dimpase]

you might want to check out the definition (7.4.1 p.323) of polar space here: ​https://drive.google.com/file/d/0B92yb82dH00zM1lNc1Y1eGVHZDQ/view?usp=sharing

that I keep in mind, instead of the wikipedia one:

A line space (P,L) is a polar space if, for each point p ∈ P and each line l ∈ L, the set of points of l which are collinear with p, is either a singleton or l.

They keep on mentioning GQs immediately after this definition, in Example 7.4.2:

Each projective space is a polar space in which, for each point p and each line l, the set of points of l collinear with p, coincides with l. At the other extreme, a generalized quadrangle is a polar space in which, for each point p and each line l not on p, the set of points of l collinear with p, is a singleton.

I edited this: ​https://en.wikipedia.org/wiki/Polar_space to begin with.

[ncohen]

Hmmmmmm... Okay.

I tend to prefer to use your definition, because it is weaker and because from the pair (s,t) one can figure use one or the other definition. Still, did you meet this definition of Generalized Quadrangle in a textbook somewhere? I would prefer to link toward something "established" in the docstring.

[ncohen]

[...] and any two vertices x,y at distance i < n have c_j(x,y) = 1.

What the hell is this c_j(x,y). Number of shortest paths? :-/

Come on, those definitions are not half as clear as those from wikipedia or from Payne and Thas' book.

Nathann

[dimpase]

Replying to ncohen:

Hmmmmmm... Okay.

I tend to prefer to use your definition, because it is weaker and because from the pair (s,t) one can figure use one or the other definition. Still, did you meet this definition of Generalized Quadrangle in a textbook somewhere? I would prefer to link toward something "established" in the docstring.

Sect. 9.6 of [BH12]_ has my definition of GQ and how it relates to parameters in on the gory details.

[git]

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

​415fffc	trac #19279: Merged with 6.9.rc0
​2a56094	trac #19279: Settling the definition issue

[ncohen]

What do you say to that? ;-)

Nathann

[dimpase]

Replying to ncohen:

[...] and any two vertices x,y at distance i < n have c_j(x,y) = 1.

What the hell is this c_j(x,y). Number of shortest paths? :-/

for x, y at distance j+1, it is number of neighbours of y in diameter j neighbourhood of x.

E.g. mu in SRG is c_2.

It is one of parameters of a distance-regular graph, no wonder it's used freely in [BCN]_

---

New commits:

​415fffc	trac #19279: Merged with 6.9.rc0
​2a56094	trac #19279: Settling the definition issue

[dimpase]

It seems that one should also say that there is at most one line on any 2 points. (Cause a general incidence system does not assume this).

I'll be mostly offline in the coming 36 hours - weekend...

[ncohen]

"Two blocks intersect on at most one point" (doc of is_generalized_quadrangle

[dimpase]

Could you merge this with the branch of #19226, which has the reference [PT09] already?

Otherwise these 2 tickets won't merge cleanly.

[dimpase]

I'm testing a merged branch now.

[dimpase]

feel free to set this to positive review if you like my branch.

---

Last 10 new commits:

​580e422	trac #19224: Merged with 6.9.beta7
​9fc78a4	trac #19224: Review
​5a0384c	trac #19224: Rework the doctests
​9433564	trac #19224: Additional doctests
​07b8da2	Merge remote-tracking branch 'trac/u/ncohen/19224' into GQ
​a14435b	Merge branch 'develop' of git://trac.sagemath.org/sage into GQ
​0780530	TL;DR: abbrvs now dead
​f8196c8	Merge remote-tracking branch 'trac/u/ncohen/19279' into GQ
​a7e6c7e	removed duplicate [PT09]
​28c24e1	referenced Wikipedia

[ncohen]

Do *NOT* merge my branchs. Ever.

[ncohen]

And please, learn to write proper commit messages which include the ticket number. Those histories are unreadable.

[git]

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

​c590ad1

trac #19279: Remove duplicate references

[ncohen]

This commit does what you requested. Observe that while the branch is not merged with #19226, the latter appears as a dependency of this ticket: this ensures that Volker will merge #19226 *first*, and so that the reference will be defined when he tests the patch.

Please do not merge again my branches with yours (until you learn to produce a readable history). Merging anything with your branches makes it impossible to review correctly.

Nathann

[dimpase]

OK. Sometimes you complain bitterly that I don't add commits, sometimes you complain bitterly that I do add commits :-)

[ncohen]

OK. Sometimes you complain bitterly that I don't add commits, sometimes you complain bitterly that I do add commits :-)

1) *propose* commits (and don't modify a branch which is not public on a ticket that is not yours) 2) Do *NOT* merge my branches. Said this thousands of times already.

Nathann