Conway's 99-graph problem

1. 辺 $uv$ を含む三角形は第 3 の頂点 $x$ で決まり、$x$ は $u,v$ の両方に隣接する頂点、すなわち $N(u)\cap N(v)$ の元である。逆に $x\in N(u)\cap N(v)$ は三角形 $uvx$ を定める。
2. $u\sim x\sim w\sim y\sim u$（$x\ne y$）の形の閉路は、$u,w$ の共通近傍の非順序対 $\{x,y\}$ で決まり、逆に共通近傍の相異なる 2 元 $x,y$ はこの形の閉路を定める（$u,w$ は隣接しないので $x,y\notin\{u,w\}$ であり、4 頂点は相異なる）。よって個数は $\binom{c}{2}$ であり、これが $1$ になるのは $c=2$ のときに限る。$\square$

$A$ を $G$ の隣接行列、$D$ を各頂点の次数 $d(v)$ を対角成分にもつ対角行列、$I$ を単位行列、$J$ を全成分 $1$ の行列とする。$(A^2)_{vw}=\sum_uA_{vu}A_{uw}$ は $v,w$ の共通近傍の個数なので、仮定により
$$A^2=D+\lambda A+\mu(J-I-A)$$
が成り立つ。$A$ は $A^2$ と可換であり、$A$ は $A$ 自身および $I$ と可換なので、$A(D+\mu J)=(D+\mu J)A$ を得る。$(AJ)_{vw}=\sum_uA_{vu}=d(v)$、$(JA)_{vw}=\sum_uA_{uw}=d(w)$ に注意して両辺の $(v,w)$ 成分を比べると
$$A_{vw}d(w)+\mu d(v)=d(v)A_{vw}+\mu d(w),\qquad\text{すなわち}\qquad(A_{vw}-\mu)(d(w)-d(v))=0.$$
$A_{vw}\in\{0,1\}$ かつ $\mu\ge2$ なので $A_{vw}-\mu\ne0$ であり、すべての $v,w$ について $d(v)=d(w)$ となる。$\square$

頂点 $v$ を固定し、$N(v)$ の頂点と $V\setminus(N(v)\cup\{v\})$ の頂点を結ぶ辺の本数を 2 通りに数える。$u\in N(v)$ の近傍は $v$、$u$ と $v$ の共通近傍 $\lambda$ 個、および残りの $k-\lambda-1$ 個からなり、残りは $v$ にも $N(v)$ にも属さない（$N(v)$ に属せば $u,v$ の共通近傍になる）。よって本数は $k(k-\lambda-1)$ である。一方 $w\notin N(v)\cup\{v\}$ は $v$ と隣接しないので $N(v)$ の中にちょうど $\mu$ 個の近傍をもち、本数は $(n-k-1)\mu$ である。$\square$

$G$ が条件 1・2 を満たすとする。prop-conway-99-reformulation により、隣接する 2 頂点の共通近傍はちょうど $1$ 個、隣接しない相異なる 2 頂点の共通近傍はちょうど $2$ 個である。$G$ は完全グラフではない（完全グラフ $K_{99}$ では各辺が $97$ 個の三角形に含まれる）し、辺のないグラフでもない（辺がなければ非隣接対を対角線とする四角形は存在しない）。prop-conway-99-regularity（$\mu=2$）により $G$ は $k$-正則であり、prop-conway-99-parameter-relation から $k(k-2)=2(98-k)$、すなわち $k^2=196$、$k=14$ を得る。よって $G$ は $\mathrm{srg}(99,14,1,2)$ である。
逆に $G$ が $\mathrm{srg}(99,14,1,2)$ ならば、$\lambda=1$、$\mu=2$ と prop-conway-99-reformulation により条件 1・2 が成り立つ。$\square$

$G$ を $\mathrm{srg}(n,k,1,2)$、$A$ をその隣接行列とする。$G$ は辺をもつので $k\ge1$ であり、辺 $uv$ は共通近傍をもつので $k\ge2$ である。$G$ は完全グラフでないので非隣接対が存在し、prop-conway-99-parameter-relation から
$$n-1=k+\frac{k(k-2)}{2}=\frac{k^2}{2}.$$
$A$ は実対称行列なので $\mathbb{R}^n$ の正規直交基底で対角化できる。全成分 $1$ のベクトル $\boldsymbol{j}$ は $A\boldsymbol{j}=k\boldsymbol{j}$ を満たし、$A$ は対称なので $\boldsymbol{j}$ の直交補空間 $\boldsymbol{j}^\perp$（次元 $n-1$）を保つ。prf-conway-99-regularity と同じ計算で $A^2=kI+A+2(J-I-A)$ であり、$x\in\boldsymbol{j}^\perp$ に対しては $Jx=0$ なので、$x$ が固有値 $\theta$ の固有ベクトルなら
$$\theta^2=k+\theta-2-2\theta,\qquad\text{すなわち}\qquad\theta^2+\theta-(k-2)=0$$
を得る。よって $\boldsymbol{j}^\perp$ 上の $A$ の固有値は $r=\dfrac{-1+\sqrt{4k-7}}{2}$ と $s=\dfrac{-1-\sqrt{4k-7}}{2}$ に限られ（$k\ge2$ より $4k-7>0$）、それぞれの重複度を $f,g$ とすると $f+g=n-1$ である。$A$ の対角成分は $0$ なので、トレースを考えて
$$k+fr+gs=0.$$
まず $4k-7$ が平方数でないとすると $\sqrt{4k-7}$ は無理数であり、$fr+gs=-\dfrac{f+g}{2}+\dfrac{(f-g)\sqrt{4k-7}}{2}=-k$ が有理数であることから $f=g$、したがって $n-1=2f$ かつ $-(n-1)/2=-k$、すなわち $n-1=2k$ となる。$n-1=k^2/2$ と合わせると $k=4$ となるが、このとき $4k-7=9$ は平方数で矛盾する。ゆえに $4k-7=m^2$ となる正の整数 $m$ があり、$m$ は奇数で $k=(m^2+7)/4$、$r=(m-1)/2$、$s=-(m+1)/2$ である。
このとき $fr+gs=\dfrac{(f-g)m}{2}-\dfrac{f+g}{2}=-k$ から
$$(f-g)m=(n-1)-2k=\frac{k^2}{2}-2k=\frac{k(k-4)}{2}=\frac{(m^2+7)(m^2-9)}{32}$$
を得る。両辺を $32$ 倍すると $32(f-g)m=(m^2+7)(m^2-9)$ なので、$m$ は $(m^2+7)(m^2-9)$ を割り切る。$(m^2+7)(m^2-9)\equiv7\cdot(-9)=-63\pmod m$ なので $m$ は $63$ を割り切り、$m\in\{1,3,7,9,21,63\}$ である。$m=1$ では $k=2$、$n=3$ となり $G$ は完全グラフ $K_3$ になって定義に反する。残りの $m=3,7,9,21,63$ が $k=4,14,22,112,994$、$n=1+k^2/2=9,99,243,6273,494019$ を与える。$\square$