Notebook

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.

In [1]:

%display latex
import drg
p = drg.DRGParameters([80, 63, 12], [1, 12, 60])
p.check_feasible()

You can also give an intersection array with parameters.

In [2]:

r = var("r")
fam = drg.DRGParameters([2*r^2*(2*r + 1), (2*r - 1)*(2*r^2 + r + 1), 2*r^2], [1, 2*r^2 , r*(4*r^2 - 1)])
fam.check_feasible()

In [3]:

fam1 = fam.subs(r == 1)
fam1

Out[3]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\text{Parameters of a distance-regular graph with intersection array } \left\{6, 4, 2; 1, 2, 3\right\}$

In [4]:

fam2 = fam.subs(r == 2)
fam2

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\text{Parameters of a distance-regular graph with intersection array } \left\{40, 33, 8; 1, 8, 30\right\}$

In [5]:

fam2.check_feasible()

---------------------------------------------------------------------------
InfeasibleError                           Traceback (most recent call last)
<ipython-input-5-58e3e45d7a79> in <module>()
----> 1 fam2.check_feasible()

/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc in check_feasible(self, checked, skip, derived, levels, queue, part)
    823             for name, check in lvl:
    824                 if name not in skip:
--> 825                     check(self)
    826                     if i > 1:
    827                         skip.add(name)

/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc in check_family(self)
   1361         nonexistence has been shown as a part of an infinite family.
   1362         """
-> 1363         self._check_family()
   1364 
   1365     @check(2)

/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc in _check_family(self)
   1626             if any(checkConditions(cond, sol) for sol in sols
   1627                    if is_integral(sol)):
-> 1628                 raise InfeasibleError(refs=ref)
   1629 
   1630     def _check_multiplicity(self, k, i):

InfeasibleError: nonexistence by JurišićVidali12

`jupyter`¶

A collection of sample Jupyter notebooks giving some nonexistence results.

Demo.ipynb - demonstration of the sage-drg package
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-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$)

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 manuscript and the repository:

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.

@article{v18a,
    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{v18b,
   AUTHOR = {Vidali, Jano\v{s}},
    TITLE = {{\tt jaanos/sage-drg}: {\tt sage-drg} v0.9},
     NOTE = {\url{https://github.com/jaanos/sage-drg/},
             \href{http://dx.doi.org/10.5281/zenodo.1418409}{\texttt{10.5281/zenodo.1418409}}},
     YEAR = {2019},
}

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, 2018. arXiv:1809.07553.

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

Distance-regular graph parameter checking in Sage¶

Contents¶

drg¶

jupyter¶

Citing¶

`drg`¶

`jupyter`¶