Opened 2 years ago
Closed 2 years ago
#29959 closed enhancement (fixed)
Extended the construction of BIBDs to allow for \lambda different from 1
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  combinatorial designs  Keywords:  bibd combinatorialdesigns 
Cc:  Dima Pasechnik  Merged in:  
Authors:  Ivo Maffei  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  a607693 (Commits, GitHub, GitLab)  Commit:  a60769317c4d0a0d601270ee1123318cebee8564 
Dependencies:  #29887  Stopgaps: 
Description (last modified by )
Extended the function balanced_incomplete_block_design
(aka BIBD) to allow arbitrary values for the parameter \lambda
.
More on BIBDs may be found here: https://en.wikipedia.org/wiki/Block_design
Change History (35)
comment:1 Changed 2 years ago by
Cc:  Dima Pasechnik added 

Status:  new → needs_review 
comment:2 Changed 2 years ago by
Reviewers:  → Dima Pasechnik 

Status:  needs_review → needs_work 
Work issues:  → correct error messages 
comment:3 Changed 2 years ago by
here is the fix  and also a fix for 2 typos:

src/sage/combinat/designs/bibd.py
a b def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 162 162 sage: designs.balanced_incomplete_block_design(1171,10) 163 163 (1171,10,1)Balanced Incomplete Block Design 164 164 165 And we know some inexistence results::165 And we know some nonexistence results:: 166 166 167 167 sage: designs.balanced_incomplete_block_design(21,6,existence=True) 168 168 False … … def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 176 176 sage: designs.balanced_incomplete_block_design(37,9,8) 177 177 (37,9,8)Balanced Incomplete Block Design 178 178 sage: designs.balanced_incomplete_block_design(15,7,3) 179 g(15,7,3)Balanced Incomplete Block Design179 (15,7,3)Balanced Incomplete Block Design 180 180 """ 181 181 182 182 # Trivial BIBD … … def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 270 270 if existence: 271 271 return Unknown 272 272 else: 273 raise NotImplementedError("I don't know how to build a ({},{}, 1)BIBD!".format(v, k))273 raise NotImplementedError("I don't know how to build a ({},{},{})BIBD!".format(v, k, lambd)) 274 274 275 275 def steiner_triple_system(n): 276 276 r"""
comment:5 Changed 2 years ago by
Description:  modified (diff) 

comment:6 Changed 2 years ago by
Commit:  b6a7f0147272177b407d518dc9628c242086e757 → 9a9705cc2292fe59816b3f3c0a9c7e8a14700406 

Branch pushed to git repo; I updated commit sha1. New commits:
9a9705c  fixed typos

comment:7 followup: 19 Changed 2 years ago by
Thanks for the review. The dockets pass, the issue with the g
is that I often start typing "git" before the os has fully switch from the editor to the console. I should definitely be more careful, but they are tricky to catch as I have run all tests before I use git.
I'll try and implement the biplane now, otherwise I will end up forgetting.
comment:8 Changed 2 years ago by
Status:  needs_work → needs_review 

comment:9 Changed 2 years ago by
not all doctests pass  namely, the following gets broken by this branch on Sage 9.1.beta2
sage t warnlong 67.2 src/sage/graphs/strongly_regular_db.pyx ********************************************************************** File "src/sage/graphs/strongly_regular_db.pyx", line 487, in sage.graphs.strongly_regular_db.is_goethals_seidel Failed example: g = t[0](*t[1:]); g Exception raised: Traceback (most recent call last): File "/mnt/opt/Sage/sageclang/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/mnt/opt/Sage/sageclang/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 1104, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.strongly_regular_db.is_goethals_seidel[5]>", line 1, in <module> g = t[Integer(0)](*t[Integer(1):]); g File "/mnt/opt/Sage/sageclang/local/lib/python3.7/sitepackages/sage/graphs/generators/families.py", line 1287, in GoethalsSeidelGraph for i in row]) File "/mnt/opt/Sage/sageclang/local/lib/python3.7/sitepackages/sage/graphs/generators/families.py", line 1287, in <listcomp> for i in row]) IndexError: pop from empty list
comment:10 Changed 2 years ago by
Status:  needs_review → needs_work 

comment:11 Changed 2 years ago by
you managed to break incidence_matrix:
sage: designs.balanced_incomplete_block_design(16,2).incidence_matrix() 16 x 240 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
it should be 16x120.
comment:12 Changed 2 years ago by
or perhaps just blocks in such a trivial case:
sage: d=designs.balanced_incomplete_block_design(3,2,1) sage: d.blocks() [[0, 1], [0, 1], [0, 2], [0, 2], [1, 2], [1, 2]]
comment:13 Changed 2 years ago by
I have fixed the issue. However, I think I'm missing something when running the doctests.
Usually, I execute sage t src/sage/combinat/designs/bibd.py
. How did you end up testing strongly_regular_db
?
Do I need to run all doctests (make ptest
) or is there a way to only test the dependencies?
comment:14 Changed 2 years ago by
I ran sage tp src/sage/combinat/
and sage tp src/sage/graphs/
Yes, ideally you should run make ptestlong
 takes time.
comment:16 Changed 2 years ago by
Commit:  9a9705cc2292fe59816b3f3c0a9c7e8a14700406 → 437afc8a6d12509b31fd3c76466349695a02eef2 

Branch pushed to git repo; I updated commit sha1. New commits:
437afc8  fixed bug with k=2

comment:18 Changed 2 years ago by
Status:  needs_work → needs_review 

Work issues:  correct error messages 
comment:19 Changed 2 years ago by
Replying to ghIvoMaffei:
I'll try and implement the biplane now, otherwise I will end up forgetting.
in any event, it makes sense to implement https://en.wikipedia.org/wiki/Bruck%E2%80%93Ryser%E2%80%93Chowla_theorem
to rule out sets of parameters for symmetric BIBDs  so far it is only done in Sage for
pojective planes, see projective_plane
in src/sage/combinat/designs/block_design.py
comment:21 Changed 2 years ago by
Status:  positive_review → needs_work 

The patchbots report pyflakes and pycodestyles errors.
comment:22 Changed 2 years ago by
If I interpret the pyflakes report correctly, it complains about ".block_design.BlockDesign imported but unused".
That's wrong as BlockDesign
is used at line 227. However, I think we could (and should) use BalancedIncompleteBlockDesign
there.
I'm now running the doctests to make sure I'm not wrong.
I fixed the pycodestyle errors, but I personally believe that code (especially the 10 lines of if ... else if ...) looked better before. Anyway, I'll push the changes as soon as the tests pass.
comment:23 Changed 2 years ago by
Thanks for explaining. I don't feel strongly about it, feel free to set back to positive review.
comment:25 Changed 2 years ago by
Commit:  437afc8a6d12509b31fd3c76466349695a02eef2 → 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
5186f8f  small code formatting

comment:26 Changed 2 years ago by
I apologise for the delay, but I finally got round to swap the BlockDesign
use to BalancedIncompleteBlockDesign
. It took longer than expected as some tests were failing, but they are completely unrelated.
comment:27 Changed 2 years ago by
Commit:  5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc → d2d340e040d05aa8be6326913576bdf7cda44d23 

Branch pushed to git repo; I updated commit sha1. New commits:
d2d340e  forgot to delete old import

comment:28 Changed 2 years ago by
a typo in docstring:
In particular, Sage can build a `(v,k,1)`BIBD when one exists for all `k\leq
there should be \lambda
instead of 1
.
comment:29 Changed 2 years ago by
a typo in docstring:
In particular, Sage can build a `(v,k,1)`BIBD when one exists for all `k\leq
there should be \lambda
instead of 1
.
Also, change the previous line
sage: BIBD = designs.balanced_incomplete_block_design(7,3)
to use (7,3,1)
.
comment:30 Changed 2 years ago by
I'll change the (7,3,1)
, but I'm not sure the other sentence should be changed.
On my computer designs.balanced_incomplete_block_design(6,3,2)
raises a NotImplementedError
and Wikipedia states that there is such a BIBD (https://en.wikipedia.org/wiki/Block_design#Examples).
comment:31 Changed 2 years ago by
Commit:  d2d340e040d05aa8be6326913576bdf7cda44d23 → a60769317c4d0a0d601270ee1123318cebee8564 

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

comment:32 Changed 2 years ago by
Status:  needs_review → positive_review 

comment:34 Changed 2 years ago by
Bibd(6,3,2) is probably another story. Not sure how it is built from what we have already
comment:35 Changed 2 years ago by
Branch:  u/ghIvoMaffei/bibd → a60769317c4d0a0d601270ee1123318cebee8564 

Resolution:  → fixed 
Status:  positive_review → closed 
looks great, adds a lot of nice stuff, but error messages need to be adjusted (lambda=1 is fixed there I suppose):
(BIBD(79,13,2) is a largest known biplane (cf. https://en.wikipedia.org/wiki/Block_design#Biplanes), so it would eventually be nice to have, but not on this ticket.