{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"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": {},
"outputs": [],
"source": [
"%display latex\n",
"import drg"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This family is not entirely feasible, however, we will find two infinite feasible subfamilies."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/html": [
""
],
"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": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {(4*r + 1)^2*(4*r - 1)*(2*r + 1), 8*(16*r^2 + 8*r - 1)*r^2, (4*r + 1)^2*r; 1, (4*r + 1)^2*r, 4*(4*r + 1)*(4*r - 1)*(2*r + 1)*r}"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/plain": [
"64*(8*r^2 + 4*r - 1)*(2*r + 1)*r^2"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pA = p.subs(t == 4*r^2)\n",
"pA.intersectionArray(expand=True, factor=True)\n",
"show(pA)\n",
"show(pA.order(expand=True, factor=True))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {(16*r^2 + 8*r - 1)*(4*r + 1)*(2*r + 1), 8*(4*r + 3)*(4*r + 1)*r^2, (4*r + 3)*(4*r + 1)*r; 1, (4*r + 3)*(4*r + 1)*r, 4*(16*r^2 + 8*r - 1)*(2*r + 1)*r}"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/plain": [
"128*(2*r + 1)^3*r^2"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pB = p.subs(t == 2*r*(2*r+1))\n",
"pB.intersectionArray(expand=True, factor=True)\n",
"show(pB)\n",
"show(pB.order(expand=True, factor=True))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {225, 184, 25; 1, 25, 180}"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/plain": [
"2112"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pA1 = pA.subs(r == 1)\n",
"show(pA1)\n",
"show(pA1.order())\n",
"pA1.check_feasible(skip=[\"family\"])"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"Parameters of a distance-regular graph with intersection array {345, 280, 35; 1, 35, 276}"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/plain": [
"3456"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pB1 = pB.subs(r == 1)\n",
"show(pB1)\n",
"show(pB1.order())\n",
"pB1.check_feasible(skip=[\"family\"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"[0, 0, 0]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p.set_vars([t, r])\n",
"pq = p.kreinParameters()\n",
"[pq[1, 1, 3], pq[1, 3, 1], pq[3, 1, 1]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"4*r"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pp = p.pTable()\n",
"pp[3, 3, 3].factor().simplify_full()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The parameter $\\alpha$ 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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"[(alpha - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
" (alpha - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
" (alpha - 4*r + 1)*(4*r + 1)/(4*r - 1),\n",
" -8*(alpha - 4*r + 1)*r/(4*r - 1),\n",
" -8*(alpha - 4*r + 1)*r/(4*r - 1),\n",
" -8*(alpha - 4*r + 1)*r/(4*r - 1)]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"alpha = var(\"alpha\")\n",
"S333 = p.tripleEquations(3, 3, 3, params={alpha: (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": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"(2*r + 1)*(4*t - 1)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"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": [
"S333a = S333.subs(alpha == 4*r - 1)\n",
"pa = p.aTable(full=True)\n",
"show(pa[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": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"4*(2*r + 1)*r*(4*t - 1)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/plain": [
"4*(2*r + 1)*r*(4*t - 1)"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pc = p.cTable(full=True)\n",
"show(pc[3].expand().factor())\n",
"show((pa[3] * pp[3, 3, 3]).expand().factor())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"2*t - 1/2"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"beta = var(\"beta\")\n",
"S123 = p.tripleEquations(1, 2, 3, params={beta: (3, 3, 3)}).subs(beta == 1)\n",
"S123[1, 1, 3]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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 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
}