Opened 5 years ago
Closed 5 years ago
#19279 closed enhancement (fixed)
IncidenceStructure.is_generalized_quadrangle
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorial designs  Keywords:  
Cc:  vdelecroix, dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  c590ad1 (Commits, GitHub, GitLab)  Commit:  c590ad18c93f7b0376145142c4da1448cda05b8f 
Dependencies:  #19277, #19226  Stopgaps: 
Description
Simple implementation. Perhaps not very optimized, but working. Until we need something more efficient.
Nathann
Change History (35)
comment:1 Changed 5 years ago by
 Branch set to u/ncohen/19279
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit set to d0fbdf19cc3fb032cab78da5b6a6b5c2b2d7c978
comment:3 Changed 5 years ago by
 Commit changed from d0fbdf19cc3fb032cab78da5b6a6b5c2b2d7c978 to 4f8a84b8f65b917883e46e28b8942ae52dd09b3d
comment:4 followup: ↓ 5 Changed 5 years ago by
1) GQs don't necessary admit parameters; e.g.
ooo    ooo
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).
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 5 years ago by
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
comment:6 in reply to: ↑ 5 Changed 5 years ago by
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...
comment:7 Changed 5 years ago by
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...
comment:8 followup: ↓ 9 Changed 5 years ago by
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
comment:9 in reply to: ↑ 8 Changed 5 years ago by
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
?
comment:10 Changed 5 years ago by
 Commit changed from 4f8a84b8f65b917883e46e28b8942ae52dd09b3d to c26038e543830f388cdceafb139d33e5f28359cd
Branch pushed to git repo; I updated commit sha1. New commits:
c26038e  trac #19279: Different definition

comment:11 followup: ↓ 12 Changed 5 years ago by
Done. Could you update the wikipedia definition?
Nathann
comment:12 in reply to: ↑ 11 Changed 5 years ago by
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/9783034802710
And I meanwhile have 5 overdue referee reports to write :)
comment:13 Changed 5 years ago by
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
comment:14 followup: ↓ 17 Changed 5 years ago by
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 ngon 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 :)
comment:15 Changed 5 years ago by
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.
comment:16 followup: ↓ 18 Changed 5 years ago by
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.
comment:17 in reply to: ↑ 14 ; followup: ↓ 21 Changed 5 years ago by
[...] 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
comment:18 in reply to: ↑ 16 Changed 5 years ago by
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.
comment:19 Changed 5 years ago by
 Commit changed from c26038e543830f388cdceafb139d33e5f28359cd to 2a5609463a71f7baab5a9f028112bab3de20fd36
comment:20 Changed 5 years ago by
What do you say to that? ;)
Nathann
comment:21 in reply to: ↑ 17 Changed 5 years ago by
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 distanceregular 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

comment:22 Changed 5 years ago by
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...
comment:23 Changed 5 years ago by
"Two blocks intersect on at most one point" (doc of is_generalized_quadrangle
)
comment:24 Changed 5 years ago by
Could you merge this with the branch of #19226, which has the reference [PT09] already?
Otherwise these 2 tickets won't merge cleanly.
comment:25 Changed 5 years ago by
 Dependencies changed from #19277 to #19277, #19226
 Reviewers set to Dima Pasechnik
I'm testing a merged branch now.
comment:26 Changed 5 years ago by
 Branch changed from u/ncohen/19279 to public/isGQ
 Commit changed from 2a5609463a71f7baab5a9f028112bab3de20fd36 to 28c24e147c70465b2ecc803e20b0b00d805a6323
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 remotetracking 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 remotetracking branch 'trac/u/ncohen/19279' into GQ

a7e6c7e  removed duplicate [PT09]

28c24e1  referenced Wikipedia

comment:27 Changed 5 years ago by
Do *NOT* merge my branchs. Ever.
comment:28 Changed 5 years ago by
 Branch changed from public/isGQ to u/ncohen/19279
 Commit changed from 28c24e147c70465b2ecc803e20b0b00d805a6323 to 2a5609463a71f7baab5a9f028112bab3de20fd36
comment:29 Changed 5 years ago by
And please, learn to write proper commit messages which include the ticket number. Those histories are unreadable.
comment:30 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:31 Changed 5 years ago by
 Commit changed from 2a5609463a71f7baab5a9f028112bab3de20fd36 to c590ad18c93f7b0376145142c4da1448cda05b8f
Branch pushed to git repo; I updated commit sha1. New commits:
c590ad1  trac #19279: Remove duplicate references

comment:32 Changed 5 years ago by
 Status changed from needs_work to needs_review
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
comment:33 followup: ↓ 34 Changed 5 years ago by
 Status changed from needs_review to positive_review
OK. Sometimes you complain bitterly that I don't add commits, sometimes you complain bitterly that I do add commits :)
comment:34 in reply to: ↑ 33 Changed 5 years ago by
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
comment:35 Changed 5 years ago by
 Branch changed from u/ncohen/19279 to c590ad18c93f7b0376145142c4da1448cda05b8f
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #19227: CremonaRichmond configuration
trac #19279: IncidenceStructure.is_generalized_quadrangle