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.
import drg
p = drg.DRGParameters([80, 63, 12], [1, 12, 60])
p.check_feasible()
You can also give an intersection array with parameters.
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()
fam1 = fam.subs(r == 1)
fam1
Parameters of a distance-regular graph with intersection array {6, 4, 2; 1, 2, 3}
fam2 = fam.subs(r == 2)
fam2
Parameters of a distance-regular graph with intersection array {40, 33, 8; 1, 8, 30}
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/drg.pyc in check_feasible(self, checked, skip, derived) 674 for name, check in checks: 675 if name not in skip: --> 676 check() 677 if not derived: 678 return /home/janos/repos/git/sage-drg/drg/drg.pyc in check_family(self) 635 in zip(self.b[:-1] + self.c[1:], b + c)], vars) 636 if any(checkConditions(cond, sol) for sol in sols): --> 637 raise InfeasibleError(refs = ref) 638 639 def check_feasible(self, checked = None, skip = None, derived = True): InfeasibleError: nonexistence by JurišićVidali12
jupyter¶
A collection of sample Jupyter notebooks giving some nonexistence results.
- Demo.ipynb - demonstration of the
sage-drgpackage - 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, 10, 1; 1, 2, r^2-9, r^2-4\}$ ($r \ne 9$)
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, 2018.
arXiv:1803.10797.J. Vidali.
jaanos/sage-drg:sage-drgv0.8, 2018.https://github.com/jaanos/sage-drg/,doi:10.5281/zenodo.1418410.
@other {v18a,
AUTHOR = {Vidali, Jano\v{s}},
TITLE = {Using symbolic computation to prove nonexistence of distance-regular graphs},
NOTE = {\href{http://arxiv.org/abs/1803.10797}{\texttt{arXiv:1803.10797}}},
YEAR = {2018},
}
@software{v18b,
AUTHOR = {Vidali, Jano\v{s}},
TITLE = {{\tt jaanos/sage-drg}: {\tt sage-drg} v0.8},
NOTE = {\url{https://github.com/jaanos/sage-drg/},
\href{http://dx.doi.org/10.5281/zenodo.1418410}{\texttt{10.5281/zenodo.1418410}}},
YEAR = {2018},
}
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.