{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "notes" } }, "source": [ "This notebook is meant to be viewed as a [RISE](https://github.com/damianavila/RISE) slideshow. When run, a custom stylesheet will be applied:\n", "* *italic* text will be shown in *blue*,\n", "* **bold** text will be showin in **red**, and\n", "* ~~strikethrough~~ text will be shown in ~~green~~.\n", "\n", "The code below is meant to be run before the presentation to ensure that Sage and its dependencies are properly initialized, so no waiting is required during the presentation." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import drg\n", "p = [[[1, 0, 0, 0], [0, 6, 0, 0], [0, 0, 3, 0], [0, 0, 0, 6]],\n", " [[0, 1, 0, 0], [1, 2, 1, 2], [0, 1, 0, 2], [0, 2, 2, 2]],\n", " [[0, 0, 1, 0], [0, 2, 0, 4], [1, 0, 2, 0], [0, 4, 0, 2]],\n", " [[0, 0, 0, 1], [0, 2, 2, 2], [0, 2, 0, 1], [1, 2, 1, 2]]]\n", "scheme = drg.ASParameters(p)\n", "scheme.kreinParameters()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Computing distance-regular graph and association scheme parameters in SageMath with [`sage-drg`](https://github.com/jaanos/sage-drg)\n", "\n", "### Janoš Vidali\n", "#### University of Ljubljana\n", "\n", "
\n", "\n", "\n", "\n", "
\n", "\n", "[Live slides](https://mybinder.org/v2/gh/jaanos/sage-drg/master?filepath=jupyter/2019-07-04-fpsac/FPSAC-sage-drg.ipynb) on [Binder](https://mybinder.org)\n", "\n", "https://github.com/jaanos/sage-drg" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Association schemes\n", "\n", "* **Association schemes** were defined by *Bose* and *Shimamoto* in *1952* as a theory underlying **experimental design**.\n", "* They provide a ~~unified approach~~ to many topics, such as\n", " - *combinatorial designs*,\n", " - *coding theory*,\n", " - generalizing *groups*, and\n", " - *strongly regular* and *distance-regular graphs*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Examples\n", "\n", "* *Hamming schemes*: **$X = \\mathbb{Z}_n^d$**, **$x \\ R_i \\ y \\Leftrightarrow \\operatorname{weight}(x-y) = i$**\n", "* *Johnson schemes*: **$X = \\{S \\subseteq \\mathbb{Z}_n \\;|\\; |S| = d\\}$** ($2d \\le n$), **$x \\ R_i \\ y \\Leftrightarrow |x \\cap y| = d-i$**\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Definition\n", "\n", "* Let **$X$** be a set of *vertices* and **$\\mathcal{R} = \\{R_0 = \\operatorname{id}_X, R_1, \\dots, R_D\\}$** a set of *symmetric relations* partitioning *$X^2$*.\n", "\n", "* **$(X, \\mathcal{R})$** is said to be a **$D$-class association scheme** if there exist numbers **$p^h_{ij}$** ($0 \\le h, i, j \\le D$) such that, for any *$x, y \\in X$*,\n", "**$$\n", "x \\ R_h \\ y \\Rightarrow |\\{z \\in X \\;|\\; x \\ R_i \\ z \\ R_j \\ y\\}| = p^h_{ij}\n", "$$**\n", "\n", "* We call the numbers **$p^h_{ij}$** ($0 \\le h, i, j \\le D$) **intersection numbers**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Main problem\n", "\n", "* Does an association scheme with given parameters ~~exist~~?\n", " - If so, is it ~~unique~~?\n", " - Can we determine ~~all~~ such schemes?\n", "* ~~Lists~~ of feasible parameter sets have been compiled for [**strongly regular**](https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html) and [**distance-regular graphs**](https://www.win.tue.nl/~aeb/drg/drgtables.html).\n", "* Recently, lists have also been compiled for some [**$Q$-polynomial association schemes**](http://www.uwyo.edu/jwilliford/).\n", "* Computer software allows us to *efficiently* compute parameters and check for *existence conditions*, and also to obtain new information which would be helpful in the ~~construction~~ of new examples." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Bose-Mesner algebra\n", "\n", "* Let **$A_i$** be the *binary matrix* corresponding to the relation *$R_i$* ($0 \\le i \\le D$).\n", "\n", "* The vector space **$\\mathcal{M}$** over *$\\mathbb{R}$* spanned by *$A_i$* ($0 \\le i \\le D$) is called the **Bose-Mesner algebra**.\n", "\n", "* *$\\mathcal{M}$* has a second basis ~~$\\{E_0, E_1, \\dots, E_D\\}$~~ consisting of *projectors* to the *common eigenspaces* of *$A_i$* ($0 \\le i \\le D$).\n", "\n", "* There are ~~nonnegative~~ constants **$q^h_{ij}$**, called **Krein parameters**, such that\n", "**$$\n", "E_i \\circ E_j = {1 \\over |X|} \\sum_{h=0}^d q^h_{ij} E_h ,\n", "$$**\n", "where **$\\circ$** is the *entrywise matrix product*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Parameter computation: general association schemes" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "%display latex\n", "import drg\n", "p = [[[1, 0, 0, 0], [0, 6, 0, 0], [0, 0, 3, 0], [0, 0, 0, 6]],\n", " [[0, 1, 0, 0], [1, 2, 1, 2], [0, 1, 0, 2], [0, 2, 2, 2]],\n", " [[0, 0, 1, 0], [0, 2, 0, 4], [1, 0, 2, 0], [0, 4, 0, 2]],\n", " [[0, 0, 0, 1], [0, 2, 2, 2], [0, 2, 0, 1], [1, 2, 1, 2]]]\n", "scheme = drg.ASParameters(p)\n", "scheme.kreinParameters()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Metric and cometric schemes\n", "\n", "* If **$p^h_{ij} \\ne 0$** (resp. **$q^h_{ij} \\ne 0$**) implies **$|i-j| \\le h \\le i+j$**, then the association scheme is said to be **metric** (resp. **cometric**).\n", "\n", "* The *parameters* of a *metric* association scheme can be ~~determined~~ from the **intersection array**\n", "*$$\n", "\\{b_0, b_1, \\dots, b_{D-1}; c_1, c_2, \\dots, c_D\\}\n", "\\quad (b_i = p^i_{1,i+1}, c_i = p^i_{1,i-1}).\n", "$$*\n", "\n", "* The *parameters* of a *cometric* association scheme can be ~~determined~~ from the **Krein array**\n", "*$$\n", "\\{b^*_0, b^*_1, \\dots, b^*_{D-1}; c^*_1, c^*_2, \\dots, c^*_D\\}\n", "\\quad (b^*_i = q^i_{1,i+1}, c^*_i = q^i_{1,i-1}).\n", "$$*\n", "\n", "* *Metric* association schemes correspond to *distance-regular graphs*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Parameter computation: metric and cometric schemes" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from drg import DRGParameters\n", "syl = DRGParameters([5, 4, 2], [1, 1, 4])\n", "syl" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "syl.order()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "from drg import QPolyParameters\n", "q225 = QPolyParameters([24, 20, 36/11], [1, 30/11, 24])\n", "q225" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "q225.order()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "syl.pTable()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "syl.kreinParameters()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "syl.distancePartition()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "syl.distancePartition(1)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Parameter computation: parameters with variables\n", "\n", "Let us define a *one-parametric family* of *intersection arrays*." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "r = var(\"r\")\n", "f = 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", "f" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "f1 = f.subs(r == 1)\n", "f1" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The parameters of `f1` are known to ~~uniquely determine~~ the *Hamming scheme $H(3, 3)$*." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "f2 = f.subs(r == 2)\n", "f2" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Feasibility checking\n", "\n", "A parameter set is called **feasible** if it passes all known *existence conditions*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us verify that *$H(3, 3)$* is feasible." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "f1.check_feasible()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "No error has occured, since all existence conditions are met." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us now check whether the second member of the family is feasible." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "f2.check_feasible()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In this case, ~~nonexistence~~ has been shown by *matching* the parameters against a list of **nonexistent families**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Triple intersection numbers\n", "\n", "* In some cases, **triple intersection numbers** can be computed.\n", "* ~~Nonexistence~~ of some *$Q$-polynomial* association schemes has been proven by obtaining a *contradiction* in *double counting* with triple intersection numbers." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "q225.check_quadruples()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Integer linear programming* has been used to find solutions to multiple systems of *linear Diophantine equations*,\n", "*eliminating* inconsistent solutions." ] } ], "metadata": { "celltoolbar": "Slideshow", "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" }, "livereveal": { "transition": "none" }, "rise": { "transition": "none" } }, "nbformat": 4, "nbformat_minor": 2 }