{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Nonexistence of a distance-regular graph with intersection array $\\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\\}$\n",
    "\n",
    "We will show that a distance-regular graph with intersection array $\\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\\}$, where $r, t \\ge 1$, does not exist. The intersection array arises for graphs of diameter $3$ with $b_2 = c_2$ and $p^3_{33}$ even which are $Q$-polynomial with respect to the natural ordering of eigenvalues and contain a maximal $1$-code that is both locally regular and last subconstituent perfect. See [Extremal $1$-codes in distance-regular graphs of diameter $3$](http://link.springer.com/article/10.1007/s10623-012-9651-0) by A. Jurišić and J. Vidali, where the theory for dealing with such intersection arrays has been developed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import drg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "This family is not entirely feasible, however, we will find two infinite feasible subfamilies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8*(16*r^2*t - 4*r^2 + 12*r*t - 2*r + t)*(2*r + 1)*t/(r + t)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r, t = var(\"r t\")\n",
    "p = drg.DRGParameters([(2*r+1)*(4*r+1)*(4*t-1), 8*r*(4*r*t-r+2*t), (r+t)*(4*r+1)],\n",
    "     [1, (r+t)*(4*r+1), 4*r*(2*r+1)*(4*t-1)])\n",
    "p.order(expand = True, factor = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The two feasible subfamilies can be obtained by setting $t = 4r^2$ and $t = 2r(2r+1)$, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameters of a distance-regular graph with intersection array {(16*r^2 - 1)*(4*r + 1)*(2*r + 1), 8*(16*r^3 + 8*r^2 - r)*r, (4*r^2 + r)*(4*r + 1); 1, (4*r^2 + r)*(4*r + 1), 4*(16*r^2 - 1)*(2*r + 1)*r}\n",
      "64*(8*r^2 + 4*r - 1)*(2*r + 1)*r^2\n"
     ]
    }
   ],
   "source": [
    "pa = p.subs(t == 4*r^2)\n",
    "print(pa)\n",
    "print(pa.order(expand = True, factor = True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameters of a distance-regular graph with intersection array {(8*(2*r + 1)*r - 1)*(4*r + 1)*(2*r + 1), 8*(8*(2*r + 1)*r^2 + 4*(2*r + 1)*r - r)*r, (2*(2*r + 1)*r + r)*(4*r + 1); 1, (2*(2*r + 1)*r + r)*(4*r + 1), 4*(8*(2*r + 1)*r - 1)*(2*r + 1)*r}\n",
      "128*(2*r + 1)^3*r^2\n"
     ]
    }
   ],
   "source": [
    "pb = p.subs(t == 2*r*(2*r+1))\n",
    "print(pb)\n",
    "print(pb.order(expand = True, factor = True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let us check that the first members of each family are indeed feasible. We skip the family nonexistence check since the intersection array of the entire family is already included."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameters of a distance-regular graph with intersection array {225, 184, 25; 1, 25, 180}\n",
      "2112\n"
     ]
    }
   ],
   "source": [
    "pa1 = pa.subs(r == 1)\n",
    "print(pa1)\n",
    "print(pa1.order())\n",
    "pa1.check_feasible(skip = [\"family\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameters of a distance-regular graph with intersection array {345, 280, 35; 1, 35, 276}\n",
      "3456\n"
     ]
    }
   ],
   "source": [
    "pb1 = pb.subs(r == 1)\n",
    "print(pb1)\n",
    "print(pb1.order())\n",
    "pb1.check_feasible(skip = [\"family\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "We now compute the Krein parameters. We have $q^1_{13} = q^1_{31} = q^3_{11} = 0$, so the graph would be $Q$-polynomial with respect to the natural ordering of the eigenvalues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.set_vars([t, r])\n",
    "p.kreinParameters()\n",
    "[p.q[1, 1, 3], p.q[1, 3, 1], p.q[3, 1, 1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "We now compute the triple intersection numbers with respect to three vertices $u, v, w$ at mutual distances $3$. Let us first check that $p^3_{33}$ is positive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4*r"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.p[3, 3, 3].expand().factor()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The parameter $a$ will denote the number of vertices at distance $3$ from all of $u, v, w$. Let us count the number of vertices at distance $1$ or $2$ from one of $u, v, w$ and $3$ from the other two vertices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(a - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
       " (a - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
       " (a - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
       " -8*(a - 4*r + 1)*r/(4*r - 1),\n",
       " -8*(a - 4*r + 1)*r/(4*r - 1),\n",
       " -8*(a - 4*r + 1)*r/(4*r - 1)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S333 = p.tripleEquations(3, 3, 3, params = {\"a\": (3, 3, 3)})\n",
    "[S333[s].expand().factor() for s in [(1, 3, 3), (3, 1, 3), (3, 3, 1), (2, 3, 3), (3, 2, 3), (3, 3, 2)]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Note that for the above expressions to be nonnegative, we must have $a = 4r - 1$, and then they are all equal to zero. Consequently, all of the $a_3$ vertices adjacent to one of $u, v, w$ which are at distance $3$ from another of these vertices are at distance $2$ from the remaining vertex in the triple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2*r + 1)*(4*t - 1)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2*r + 1)*(4*t - 1),\n",
       " (2*r + 1)*(4*t - 1),\n",
       " (2*r + 1)*(4*t - 1),\n",
       " (2*r + 1)*(4*t - 1),\n",
       " (2*r + 1)*(4*t - 1),\n",
       " (2*r + 1)*(4*t - 1)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = S333[3, 3, 3]\n",
    "S333a = S333.subs(a == 4*r - 1)\n",
    "print(p.a[3].expand().factor())\n",
    "[S333a[s].expand().factor() for s in [(1, 2, 3), (3, 1, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (1, 3, 2)]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The above results mean that any two vertices $v, w$ at distance $3$ uniquely define a set $C$ of $4r + 2$ vertices mutually at distance $3$ containing $v, w$ - i.e., a $1$-code in the graph. Furthermore, since $a_3$ is nonzero, for each $u$ in $C \\setminus \\{v, w\\}$, there are vertices at distances $3, 1, 2$ from $u, v, w$. We now check that $c_3 = a_3 p^3_{33}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4*(2*r + 1)*r*(4*t - 1)\n",
      "4*(2*r + 1)*r*(4*t - 1)\n"
     ]
    }
   ],
   "source": [
    "print(p.c[3].expand().factor())\n",
    "print((p.a[3] * p.p[3, 3, 3]).expand().factor())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let $u'$ be a neighbour of $v$. Since $u'$ is not in $C$, it may be at distance $3$ from at most one vertex of $C$. As there are $c_3$ and $a_3$ neighbours of $v$ that are at distances $2$ and $3$ from $w$, respectively, the above equality implies that each neighbour of $v$ is at distance $3$ from precisely one vertex of $C$.\n",
    "\n",
    "Suppose now that $u'$ is at distance 2 from $w$. Let us count the number of vertices at distances $1, 1, 3$ from $u', v, w$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*t - 1/2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S123 = p.tripleEquations(1, 2, 3, params = {\"b\": (3, 3, 3)})\n",
    "b = S123[3, 3, 3]\n",
    "S123b = S123.subs(b == 1)\n",
    "S123b[1, 1, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "As this value is nonintegral, we conclude that a graph with intersection array $\\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\\}$ and $r, t \\ge 1$ **does not exist**."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.6",
   "language": "",
   "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}