2020 GSoC Final report

GSoC2020.md

2020 GSoC Final report

Overview

The aim of this project is to construct a database of distance-regular graphs. In particular, we aimed at building a function graphs.distance_regular_graph which, given an intersection array, it would return a graph with such parameters. During this process, we worked on other combinatorial objects such as BIBDs, orthogonal arrays and linear codes.

At the time of writing graphs.distance_regular_graph can construct a considerable amount of sporadic examples and all known (to the best of my knowledge) families with unbounded diameter.

Trac Tickets

Contributions to the SageMath's codebase are done using their Trac server. One needs to open a Trac ticket in order to have the community to review and approve their code. In this section I'll list all Trac tickets I contributed to. I'll distinguish between closed (i.e. completed) tickets and open tickets (these may need some work before being approved).

Closed Tickets

1. #29887 small bug fix in a database of balanced incomplete block designs;
2. #29959 SageMath can build BIBDs via the function desings.balanced_incomplete_block_design(v, k), this ticket extends that function to allow for arbitrary values of , while before was fixed to 1;
3. #30004 constructed the BIBDs with parameters (79, 13, 2) and (56, 11, 2);
4. #30016 added a function designs.biplane(n) that constructus a biplane of order n;
5. #30029 added a nonexistence check for BIBDs based on the Bruck–Ryser–Chowla theorem;
6. #30037 added a recursive construction that builds a -BIBD from a symmetric -BIBD;
7. #30085 implemented the Kasami codes;
8. #30102 fix a bug where designs.difference_family did not handle trivial or invalid inputs;
9. #30107 fix bugs when designs.balance_incomplete_block_design used the optional argument use_LJCR=True;
10. #30240 added the distance_regular module to SageMath and implemented 4 sporadic distance-regular graphs;
11. #30253 added a method to compute the coset grah of a linear coder;
12. #30260 added 6 sporadic distance-regular graphs;
13. #30279 fixed outdated parts of the FAQs;
14. #30286 added 5 sporadic distance-regular graphs;
15. #30301 updated and corrected the Italian translation of the FAQs;
16. #30303 added two families of distance-regular graphs with unbounded diameter;
17. #30355 added a method to compute the bipartite double and the extended bipartite double of an undirected graph;

Open Tickets

1. #29410 added a few constructions for difference matrices whose value is not 1. Also expanded the generation of related objects such as orthogonal arrays, to take advantage of the new constructions;
2. #29866 added a method to enumerate all symmetric matrices of a matrix space;
3. #30033 created function designs.two_graph which groups all constructions of two-graphs already in SageMath;
4. #30090 implemented a function to test all BIBDs constructions known to SageMath;
5. #30142 introduced association schemes to SageMath via methods to implement specifc families of them;
6. #30223 added functions to handle generalised quadrangles with spreads/ovoids and implemented a family of GQs with spread;
7. #30312 added 3 infinite families of distance-regular graphs with classical parameters;
8. #30329 added 4 infinite families of distance-regular graphs;
9. #30337 added functions to obtain distance-regular graphs from generalised quadrangles with spreads;
10. #30343 added functions that compute the distance-regular graphs related to the generalised polygons;
11. #30356 added the function graphs.distance_regular_graph which groups together all sporadic distance-regular graphs known to SageMath (also added many of them);
12. #30386 added all distance-regular graphs with classical parameters to the function graphs.distance_regular_graph;
13. #30394 added methods to: check if an undirected graph is antipodal; compute the antipodal graph of a graph; compute the antipodal folded graph of a graph;
14. #30414 added all distance-regular pseudo partition graphs to the function graphs.distance_regular_graph;
15. #30439 fix small bug caused by the interaction of GAP with floats;
16. #30441 added all distance-regular near polygon graphs to the function graphs.distance_regular_graph;
17. #30456 added a construction of antipodal covers of complete graphs to graphs.distance_regular_graph;

Future work

Despite the great amount of new constructions added to SageMath there are still many distance-regular graphs which are not in our module. Moreover, there are some constructions which could benefit from some optimisation as they build large graphs.

I will keep working on this project after the end of the GSoC, so this report will soon become outdated. An updated list of all tickets I've authored can be found here.

Acknowledgements

First of all, I would like to thank my supervisor Dima Pasechnik for his help throughtout this porject. His prompt answers to all of my questions and doubts helped me a lot and shaped this project. Secondly, I want to thank all the other sage developers who reviewed my tickets and proposed improvements. Finally, I would like to thank Google for sponsoring this project.