{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Distance-regular graph parameter checking in Sage\n", "\n", "[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.1418409.svg)](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": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\text{Parameters of a distance-regular graph with intersection array } \\left\\{6, 4, 2; 1, 2, 3\\right\\}$ " ], "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": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\text{Parameters of a distance-regular graph with intersection array } \\left\\{40, 33, 8; 1, 8, 30\\right\\}$ " ], "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-104-70-25-1-7-80.ipynb`](jupyter/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\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-24-20-36_11-1-30_11-24.ipynb`](jupyter/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\n", "* [`QPoly-d3-1param-odd.ipynb`](jupyter/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\n", "* [`QPoly-d4-LS-odd.ipynb`](jupyter/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\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", "* [`QPoly-d5-1param-3mod4.ipynb`](jupyter/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}$\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 paper and the software:\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`](https://doi.org/10.5281/zenodo.1418409).\n", "\n", "You may also want to cite other documents containing descriptions of features that were added since the above paper was written:\n", "\n", "* 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`](https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2019/105.pdf)\n", " + support for general and *Q*-polynomial association schemes\n", "\n", "* A. L. Gavrilyuk, J. Vidali, J. S. Williford. On few-class *Q*-polynomial association schemes: feasible parameters and nonexistence results, 2019. [`arXiv:1908.10081`](http://arxiv.org/abs/1908.10081).\n", " + triple intersection number solution finder and forbidden quadruples check\n", " + support for quadruple intersection numbers\n", "\n", "### BibTeX\n", "\n", "The above citations are given here in BibTeX format.\n", "\n", "```latex\n", "@article{v18,\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{v19a,\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{https://doi.org/10.5281/zenodo.1418409}{\\texttt{doi:10.5281/zenodo.1418409}}},\n", " YEAR = {2019},\n", "}\n", "\n", "@article{v19b,\n", " AUTHOR = {Vidali, Jano\\v{s}},\n", " TITLE = {Computing distance-regular graph and association scheme parameters in SageMath with {\\tt sage-drg}},\n", " JOURNAL = {S\\'{e}m. Lothar. Combin.},\n", " FJOURNAL = {S\\'{e}minaire Lotharingien de Combinatoire},\n", " VOLUME = {82B},\n", " PAGES = {#105},\n", " NOTE = {\\url{https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2019/105.pdf}},\n", " YEAR = {2019},\n", "}\n", "\n", "@article{gvw21,\n", " AUTHOR = {Gavrilyuk, Alexander L. and Vidali, Jano\\v{s} and Williford, Jason S.},\n", " TITLE = {On few-class $Q$-polynomial association schemes: feasible parameters and nonexistence results},\n", " JOURNAL = {Ars Math. Contemp.},\n", " FJOURNAL = {Ars Mathematica Contemporanea},\n", " NOTE = {\\href{https://doi.org/10.26493/1855-3974.2101.b76}{\\texttt{doi:10.26493/1855-3974.2101.b76}}},\n", " YEAR = {2021},\n", "}\n", "```\n", "### Other uses\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, *Combinatorica*, 40(3):345-362, 2020. [`doi:10.1007/s00493-019-4115-z`](https://doi.org/10.1007/s00493-019-4115-z).\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 }