{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Distance-regular graph parameter checking in Sage\n",
"\n",
"[](https://doi.org/10.5281/zenodo.1418409)\n",
"\n",
"A Sage package for checking the feasibility of distance-regular graph parameter sets.\n",
"A more detailed description, along with some results, is available in a [manuscript](https://arxiv.org/abs/1803.10797) currently available on arXiv."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Contents\n",
"\n",
"### `drg`\n",
"\n",
"The `drg` folder contains the package source. After you make sure that Sage sees this folder, you can import it as a Python module."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"%display latex\n",
"import drg\n",
"p = drg.DRGParameters([80, 63, 12], [1, 12, 60])\n",
"p.check_feasible()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can also give an intersection array with parameters."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"r = var(\"r\")\n",
"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)])\n",
"fam.check_feasible()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {6, 4, 2; 1, 2, 3}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fam1 = fam.subs(r == 1)\n",
"fam1"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {40, 33, 8; 1, 8, 30}"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fam2 = fam.subs(r == 2)\n",
"fam2"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"scrolled": true
},
"outputs": [
{
"ename": "InfeasibleError",
"evalue": "nonexistence by JurišićVidali12",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mInfeasibleError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfam2\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcheck_feasible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc\u001b[0m in \u001b[0;36mcheck_feasible\u001b[0;34m(self, checked, skip, derived, levels, queue, part)\u001b[0m\n\u001b[1;32m 823\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcheck\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlvl\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 824\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mname\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mskip\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 825\u001b[0;31m \u001b[0mcheck\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 826\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mi\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 827\u001b[0m \u001b[0mskip\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mname\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc\u001b[0m in \u001b[0;36mcheck_family\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 1361\u001b[0m \u001b[0mnonexistence\u001b[0m \u001b[0mhas\u001b[0m \u001b[0mbeen\u001b[0m \u001b[0mshown\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0ma\u001b[0m \u001b[0mpart\u001b[0m \u001b[0mof\u001b[0m \u001b[0man\u001b[0m \u001b[0minfinite\u001b[0m \u001b[0mfamily\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1362\u001b[0m \"\"\"\n\u001b[0;32m-> 1363\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_check_family\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1364\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1365\u001b[0m \u001b[0;34m@\u001b[0m\u001b[0mcheck\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m/home/janos/repos/git/sage-drg/drg/assoc_scheme.pyc\u001b[0m in \u001b[0;36m_check_family\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 1626\u001b[0m if any(checkConditions(cond, sol) for sol in sols\n\u001b[1;32m 1627\u001b[0m if is_integral(sol)):\n\u001b[0;32m-> 1628\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mInfeasibleError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrefs\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mref\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1629\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1630\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_check_multiplicity\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mInfeasibleError\u001b[0m: nonexistence by JurišićVidali12"
]
}
],
"source": [
"fam2.check_feasible()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `jupyter`\n",
"\n",
"A collection of sample Jupyter notebooks giving some nonexistence results.\n",
"\n",
"* [`Demo.ipynb`](jupyter/Demo.ipynb) - demonstration of the `sage-drg` package\n",
"* [`DRG-135-128-16-1-16-120.ipynb`](jupyter/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\n",
"* [`DRG-234-165-12-1-30-198.ipynb`](jupyter/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\n",
"* [`DRG-55-54-50-35-10-bipartite.ipynb`](jupyter/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\n",
"* [`DRG-d3-2param.ipynb`](jupyter/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$)\n",
"* [`QPoly-d4-tight4design.ipynb`](jupyter/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$)\n",
"\n",
"A conference presentation is also available as a [RISE](https://github.com/damianavila/RISE) slideshow.\n",
"\n",
"* [`FPSAC-sage-drg.ipynb`](jupyter/2019-07-04-fpsac/FPSAC-sage-drg.ipynb) - *Computing distance-regular graph and association scheme parameters in SageMath with `sage-drg`* software presentation at FPSAC 2019, Ljubljana, Slovenia"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Citing\n",
"\n",
"If you use `sage-drg` in your research, please cite both the manuscript and the repository:\n",
"\n",
"* 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`](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p21).\n",
"\n",
"* J. Vidali. `jaanos/sage-drg`: `sage-drg` v0.9, 2019. [`https://github.com/jaanos/sage-drg/`](https://github.com/jaanos/sage-drg/), [`doi:10.5281/zenodo.1418409`](http://dx.doi.org/10.5281/zenodo.1418409).\n",
"\n",
"```latex\n",
"@article{v18a,\n",
" AUTHOR = {Vidali, Jano\\v{s}},\n",
" TITLE = {Using symbolic computation to prove nonexistence of distance-regular graphs},\n",
" JOURNAL = {Electron. J. Combin.},\n",
" FJOURNAL = {Electronic Journal of Combinatorics},\n",
" VOLUME = {25},\n",
" NUMBER = {4},\n",
" PAGES = {P4.21},\n",
" NOTE = {\\url{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p21}},\n",
" YEAR = {2018},\n",
"}\n",
"\n",
"@software{v18b,\n",
" AUTHOR = {Vidali, Jano\\v{s}},\n",
" TITLE = {{\\tt jaanos/sage-drg}: {\\tt sage-drg} v0.9},\n",
" NOTE = {\\url{https://github.com/jaanos/sage-drg/},\n",
" \\href{http://dx.doi.org/10.5281/zenodo.1418409}{\\texttt{10.5281/zenodo.1418409}}},\n",
" YEAR = {2019},\n",
"}\n",
"```\n",
"\n",
"Additionally, `sage-drg` has been used in the following research:\n",
"\n",
"* A. Gavrilyuk, S. Suda and J. Vidali. On tight 4-designs in Hamming association schemes, 2018. [`arXiv:1809.07553`](http://arxiv.org/abs/1809.07553).\n",
"\n",
"If you would like your research to be listed here, feel free to open an issue or pull request."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 8.9.beta2",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.15"
}
},
"nbformat": 4,
"nbformat_minor": 2
}