Distance-regular graph parameter checking in Sage¶

A Sage package for checking the feasibility of distance-regular graph parameter sets. A more detailed description, along with some results, is available in a manuscript currently available on arXiv.

Contents¶

drg¶

The drg folder contains the package source. After you make sure that Sage sees this folder, you can import it as a Python module.

You can also give an intersection array with parameters.

jupyter¶

A collection of sample Jupyter notebooks giving some nonexistence results.

• Demo.ipynb - demonstration of the sage-drg package
• DRG-104-70-25-1-7-80.ipynb - proof of nonexistence of a distance-regular graph with intersection array $\{104, 70, 25; 1, 7, 80\}$ with $1470$ vertices
• DRG-135-128-16-1-16-120.ipynb - proof of nonexistence of a distance-regular graph with intersection array $\{135, 128, 16; 1, 16, 120\}$ with $1360$ vertices
• DRG-234-165-12-1-30-198.ipynb - proof of nonexistence of a distance-regular graph with intersection array $\{234, 165, 12; 1, 30, 198\}$ with $1600$ vertices
• DRG-55-54-50-35-10-bipartite.ipynb - proof of nonexistence of a bipartite distance-regular graph with intersection array $\{55, 54, 50, 35, 10; 1, 5, 20, 45, 55\}$ with $3500$ vertices
• DRG-d3-2param.ipynb - proof of nonexistence of a family of distance-regular graphs with intersection arrays $\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}$ ($r, t \ge 1$)
• QPoly-24-20-36_11-1-30_11-24.ipynb - proof of nonexistence of a $Q$-polynomial association scheme with Krein array $\{24, 20, 36/11; 30/11, 24\}$ with $225$ vertices
• QPoly-d3-1param-odd.ipynb - proof of nonexistence of a $Q$-polynomial association scheme with Krein array $\{2r^2-1, 2r^2-2, r^2+1; 1, 2, r^2-1\}$ and $r$ odd
• QPoly-d4-LS-odd.ipynb - proof of nonexistence of a $Q$-polynomial association scheme with Krein array $\{m, m-1, m(r^2-1)/r^2, m-r^2+1; 1, m/r^2, r^2-1, m\}$ and $m$ odd
• QPoly-d4-tight4design.ipynb - proof of nonexistence of a $Q$-polynomial association scheme with Krein array $\{r^2-4, r^2-9, 12(s-1)/s, 1; 1, 12/s, r^2-9, r^2-4\}$ ($s \ge 4$)
• QPoly-d5-1param-3mod4.ipynb - proof of nonexistence of a $Q$-polynomial association scheme with Krein array $\{(r^2+1)/2, (r^2-1)/2, (r^2+1)^2/(2r(r+1)), (r-1)(r^2+1)/(4r), (r^2+1)/(2r); 1, (r-1)(r^2+1)/(2r(r+1)), (r+1)(r^2+1)/(4r), (r-1)(r^2+1)/(2r), (r^2+1)/2\}$ and $r \equiv 3 \pmod{4}$

A conference presentation is also available as a RISE slideshow.

• FPSAC-sage-drg.ipynb - Computing distance-regular graph and association scheme parameters in SageMath with sage-drg software presentation at FPSAC 2019, Ljubljana, Slovenia

Citing¶

If you use sage-drg in your research, please cite both the paper and the software:

• J. Vidali. Using symbolic computation to prove nonexistence of distance-regular graphs. Electron. J. Combin., 25(4)#P4.21, 2018. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p21.

• J. Vidali. jaanos/sage-drg: sage-drg v0.9, 2019. https://github.com/jaanos/sage-drg/, doi:10.5281/zenodo.1418409.

You may also want to cite other documents containing descriptions of features that were added since the above paper was written:

• J. Vidali. Computing distance-regular graph and association scheme parameters in SageMath with sage-drg. Sém. Lothar. Combin. 82B#105, 2019. https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2019/105.pdf

  • support for general and Q-polynomial association schemes

• A. L. Gavrilyuk, J. Vidali, J. S. Williford. On few-class Q-polynomial association schemes: feasible parameters and nonexistence results, 2019. arXiv:1908.10081.

  • triple intersection number solution finder and forbidden quadruples check
  • support for quadruple intersection numbers

BibTeX¶

The above citations are given here in BibTeX format.

@article{v18,
    AUTHOR = {Vidali, Jano\v{s}},
     TITLE = {Using symbolic computation to prove nonexistence of distance-regular graphs},
   JOURNAL = {Electron. J. Combin.},
  FJOURNAL = {Electronic Journal of Combinatorics},
    VOLUME = {25},
    NUMBER = {4},
     PAGES = {P4.21},
      NOTE = {\url{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p21}},
      YEAR = {2018},
}

@software{v19a,
   AUTHOR = {Vidali, Jano\v{s}},
    TITLE = {{\tt jaanos/sage-drg}: {\tt sage-drg} v0.9},
     NOTE = {\url{https://github.com/jaanos/sage-drg/},
             \href{https://doi.org/10.5281/zenodo.1418409}{\texttt{doi:10.5281/zenodo.1418409}}},
     YEAR = {2019},
}

@article{v19b,
    AUTHOR = {Vidali, Jano\v{s}},
     TITLE = {Computing distance-regular graph and association scheme parameters in SageMath with {\tt sage-drg}},
   JOURNAL = {S\'{e}m. Lothar. Combin.},
  FJOURNAL = {S\'{e}minaire Lotharingien de Combinatoire},
    VOLUME = {82B},
     PAGES = {#105},
      NOTE = {\url{https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2019/105.pdf}},
      YEAR = {2019},
}

@article{gvw21,
    AUTHOR = {Gavrilyuk, Alexander L. and Vidali, Jano\v{s} and Williford, Jason S.},
     TITLE = {On few-class $Q$-polynomial association schemes: feasible parameters and nonexistence results},
   JOURNAL = {Ars Math. Contemp.},
  FJOURNAL = {Ars Mathematica Contemporanea},
      NOTE = {\href{https://doi.org/10.26493/1855-3974.2101.b76}{\texttt{doi:10.26493/1855-3974.2101.b76}}},
      YEAR = {2021},
}

Other uses¶

Additionally, sage-drg has been used in the following research:

• A. Gavrilyuk, S. Suda and J. Vidali. On tight 4-designs in Hamming association schemes, Combinatorica, 40(3):345-362, 2020. doi:10.1007/s00493-019-4115-z.

If you would like your research to be listed here, feel free to open an issue or pull request.