Opened 4 years ago

Closed 4 years ago

#19279 closed enhancement (fixed)

IncidenceStructure.is_generalized_quadrangle

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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) 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 4 years ago by ncohen

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

comment:2 Changed 4 years ago by git

  • Commit set to d0fbdf19cc3fb032cab78da5b6a6b5c2b2d7c978

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

5fbd6a3trac #19227: Cremona-Richmond configuration
d0fbdf1trac #19279: IncidenceStructure.is_generalized_quadrangle

comment:3 Changed 4 years ago by git

  • Commit changed from d0fbdf19cc3fb032cab78da5b6a6b5c2b2d7c978 to 4f8a84b8f65b917883e46e28b8942ae52dd09b3d

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

28d6c6etrac #19227: Cremona-Richmond configuration
4f8a84btrac #19279: IncidenceStructure.is_generalized_quadrangle

comment:4 follow-up: Changed 4 years ago by 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).

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

comment:6 in reply to: ↑ 5 Changed 4 years ago by 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...

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

comment:7 Changed 4 years ago by 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...

comment:8 follow-up: Changed 4 years ago by 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

comment:9 in reply to: ↑ 8 Changed 4 years ago by 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?

comment:10 Changed 4 years ago by git

  • Commit changed from 4f8a84b8f65b917883e46e28b8942ae52dd09b3d to c26038e543830f388cdceafb139d33e5f28359cd

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

c26038etrac #19279: Different definition

comment:11 follow-up: Changed 4 years ago by ncohen

Done. Could you update the wikipedia definition?

Nathann

comment:12 in reply to: ↑ 11 Changed 4 years ago by 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 :-)

comment:13 Changed 4 years ago by 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

comment:14 follow-up: Changed 4 years ago by 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 :-)

comment:15 Changed 4 years ago by 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.

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

comment:16 follow-up: Changed 4 years ago by 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.

comment:17 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by 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

comment:18 in reply to: ↑ 16 Changed 4 years ago by 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.

comment:19 Changed 4 years ago by git

  • Commit changed from c26038e543830f388cdceafb139d33e5f28359cd to 2a5609463a71f7baab5a9f028112bab3de20fd36

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

415fffctrac #19279: Merged with 6.9.rc0
2a56094trac #19279: Settling the definition issue

comment:20 Changed 4 years ago by ncohen

What do you say to that? ;-)

Nathann

comment:21 in reply to: ↑ 17 Changed 4 years ago by 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:

415fffctrac #19279: Merged with 6.9.rc0
2a56094trac #19279: Settling the definition issue

comment:22 Changed 4 years ago by 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...

comment:23 Changed 4 years ago by ncohen

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

Last edited 4 years ago by ncohen (previous) (diff)

comment:24 Changed 4 years ago by dimpase

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

  • Dependencies changed from #19277 to #19277, #19226
  • Reviewers set to Dima Pasechnik

I'm testing a merged branch now.

comment:26 Changed 4 years ago by dimpase

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

580e422trac #19224: Merged with 6.9.beta7
9fc78a4trac #19224: Review
5a0384ctrac #19224: Rework the doctests
9433564trac #19224: Additional doctests
07b8da2Merge remote-tracking branch 'trac/u/ncohen/19224' into GQ
a14435bMerge branch 'develop' of git://trac.sagemath.org/sage into GQ
0780530TL;DR: abbrvs now dead
f8196c8Merge remote-tracking branch 'trac/u/ncohen/19279' into GQ
a7e6c7eremoved duplicate [PT09]
28c24e1referenced Wikipedia

comment:27 Changed 4 years ago by ncohen

Do *NOT* merge my branchs. Ever.

comment:28 Changed 4 years ago by ncohen

  • Branch changed from public/isGQ to u/ncohen/19279
  • Commit changed from 28c24e147c70465b2ecc803e20b0b00d805a6323 to 2a5609463a71f7baab5a9f028112bab3de20fd36

comment:29 Changed 4 years ago by ncohen

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

comment:30 Changed 4 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:31 Changed 4 years ago by git

  • Commit changed from 2a5609463a71f7baab5a9f028112bab3de20fd36 to c590ad18c93f7b0376145142c4da1448cda05b8f

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

c590ad1trac #19279: Remove duplicate references

comment:32 Changed 4 years ago by ncohen

  • 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 follow-up: Changed 4 years ago by dimpase

  • 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 4 years ago by 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

comment:35 Changed 4 years ago by vbraun

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