Opened 3 years ago

Closed 3 years ago

# Extended the construction of BIBDs to allow for \lambda different from 1

Reported by: Owned by: gh-Ivo-Maffei major sage-9.2 combinatorial designs bibd combinatorial-designs dimpase Ivo Maffei Dima Pasechnik N/A a607693 a60769317c4d0a0d601270ee1123318cebee8564 #29887

### GitHub link to the corresponding issue

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

### comment:1 Changed 3 years ago by gh-Ivo-Maffei

Cc: dimpase added new → needs_review

### comment:2 Changed 3 years ago by dimpase

Reviewers: → Dima Pasechnik needs_review → needs_work → correct error messages

looks great, adds a lot of nice stuff, but error messages need to be adjusted (lambda=1 is fixed there I suppose):

sage: designs.balanced_incomplete_block_design(79,13,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-5-1a5677b9322f> in <module>()
----> 1 designs.balanced_incomplete_block_design(Integer(79),Integer(13),Integer(2))

/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/combinat/designs/bibd.py in balanced_incomplete_block_design(v, k, lambd, existence, use_LJCR)
271         return Unknown
272     else:
--> 273         raise NotImplementedError("I don't know how to build a ({},{},1)-BIBD!".format(v, k))
274
275 def steiner_triple_system(n):

NotImplementedError: I don't know how to build a (79,13,1)-BIBD!


(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.

### comment:3 Changed 3 years ago by dimpase

here is the fix - and also a fix for 2 typos:

• ## src/sage/combinat/designs/bibd.py

 a def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa sage: designs.balanced_incomplete_block_design(1171,10) (1171,10,1)-Balanced Incomplete Block Design And we know some inexistence results:: And we know some nonexistence results:: sage: designs.balanced_incomplete_block_design(21,6,existence=True) False def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa sage: designs.balanced_incomplete_block_design(37,9,8) (37,9,8)-Balanced Incomplete Block Design sage: designs.balanced_incomplete_block_design(15,7,3) g(15,7,3)-Balanced Incomplete Block Design (15,7,3)-Balanced Incomplete Block Design """ # Trivial BIBD def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa if existence: return Unknown else: raise NotImplementedError("I don't know how to build a ({},{},1)-BIBD!".format(v, k)) raise NotImplementedError("I don't know how to build a ({},{},{})-BIBD!".format(v, k, lambd)) def steiner_triple_system(n): r"""
Last edited 3 years ago by dimpase (previous) (diff)

### comment:4 Changed 3 years ago by dimpase

the typo with extra g tells me that you didn't run doctests :-)

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

### comment:5 Changed 3 years ago by dimpase

Description: modified (diff)

### comment:6 Changed 3 years ago by git

Commit: b6a7f0147272177b407d518dc9628c242086e757 → 9a9705cc2292fe59816b3f3c0a9c7e8a14700406

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

 ​9a9705c fixed typos

### comment:7 follow-up:  19 Changed 3 years ago by gh-Ivo-Maffei

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 3 years ago by gh-Ivo-Maffei

Status: needs_work → needs_review

### comment:9 Changed 3 years ago by dimpase

not all doctests pass - namely, the following gets broken by this branch on Sage 9.1.beta2

sage -t --warn-long 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/sage-clang/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/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/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in GoethalsSeidelGraph
for i in row])
File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in <listcomp>
for i in row])
IndexError: pop from empty list


### comment:10 Changed 3 years ago by dimpase

Status: needs_review → needs_work

### comment:11 Changed 3 years ago by dimpase

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

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 3 years ago by gh-Ivo-Maffei

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

I tested sage -tp src/sage/combinat/ and sage -tp src/sage/graphs/ Yes, ideally you should run make ptestlong - takes time.

Version 0, edited 3 years ago by dimpase (next)

### comment:15 Changed 3 years ago by dimpase

don't forget to push the fixes.

### comment:16 Changed 3 years ago by git

Commit: 9a9705cc2292fe59816b3f3c0a9c7e8a14700406 → 437afc8a6d12509b31fd3c76466349695a02eef2

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

 ​437afc8 fixed bug with k=2

### comment:17 Changed 3 years ago by gh-Ivo-Maffei

I run make ptest this time and all seem to work.

### comment:18 Changed 3 years ago by gh-Ivo-Maffei

Status: needs_work → needs_review correct error messages

### comment:19 in reply to:  7 Changed 3 years ago by dimpase

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:20 Changed 3 years ago by dimpase

Status: needs_review → positive_review

OK, good.

### comment:21 Changed 3 years ago by slelievre

Status: positive_review → needs_work

The patchbots report pyflakes and pycodestyles errors.

### comment:22 Changed 3 years ago by gh-Ivo-Maffei

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 3 years ago by slelievre

Thanks for explaining. I don't feel strongly about it, feel free to set back to positive review.

### comment:24 Changed 3 years ago by dimpase

Status: needs_work → positive_review

OK.

### comment:25 Changed 3 years ago by git

Commit: 437afc8a6d12509b31fd3c76466349695a02eef2 → 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc 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 3 years ago by gh-Ivo-Maffei

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 3 years ago by git

Commit: 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc → d2d340e040d05aa8be6326913576bdf7cda44d23

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

 ​d2d340e forgot to delete old import

### comment:28 Changed 3 years ago by dimpase

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

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 3 years ago by gh-Ivo-Maffei

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 3 years ago by git

Commit: d2d340e040d05aa8be6326913576bdf7cda44d23 → a60769317c4d0a0d601270ee1123318cebee8564

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

 ​a607693 changed docstring

### comment:32 Changed 3 years ago by dimpase

Status: needs_review → positive_review

OK

### comment:34 Changed 3 years ago by dimpase

Bibd(6,3,2) is probably another story. Not sure how it is built from what we have already

### comment:35 Changed 3 years ago by vbraun

Branch: u/gh-Ivo-Maffei/bibd → a60769317c4d0a0d601270ee1123318cebee8564 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.