12 Strongly Regular Graph

Our bound on ${\lambda }_2$ and ${\lambda }_n$ in $d$-regular graphs can only be exact, if ${\lambda }_1,{\lambda }_2,{\lambda }_n$ are all distinct eigenvalues.

What are such graphs?

A different POV: we call an eigenvalue of a regular graph restricted if it has an eigenvector in $j^{\perp }$.

How many distinct restricted eigenvalues are needed for intersesting examples?

$0$ restricted eigenvalues: only $K_1$.

$1$ restricted eigenvalues: degree $d$, restricted eigenvalue $\lambda$ with multiplicity $n-1$. Then we have

• $0=\mathrm{tr}(A)=d+(n-1)\lambda$
• $nd=\mathrm{tr}(A^2)=d^2+(n-1){\lambda }^2$.

It follows that $(d,\lambda )\in \{(n-1,-1),(0,0)\}$, which corresponds to $K_n$ and $\overline{K_n}$, respectively.

Definition

A strongly regular graph is a (finite) regular graph with precisely two restricted eigenvalues. Let $k,r,s$ denote its eigenvalues, $k$ is the eigenvalues of $j$, $k⩾r⩾s$.

Lemma

This definition is equivalent to ^xfbbko.

\begin{proof} Let $\Gamma$ be an SRG with $k,r,s$ as ^88eu0u. Clearly, $AJ=JA=kJ$. Also $(A-rI)(A-sI)=\mu J$. 为什么 Thus $A^2\in ⟨A,I,J⟩$ and so $A^2=\kappa I+\lambda A+\mu (J-I-A)$ for some constant $\kappa ,\lambda ,\mu$.

As the diagonal entries of $A^2$ are all $k$, we know $\kappa =k$. Clearly, $\lambda$ and $\mu$ have the asserted combinatorial meaning as in ^xfbbko. \end{proof}

Remark. Comparing coefficients, we find $\lambda =\mu +r+s$ and $k-\mu =-rs$. We say that $\Gamma$ has parameters $(v,k,\lambda ,\mu )$. Note:

• The complete and edgeless graphs are not SRGs according to ^88eu0u.
• Complete multipartite graphs and their complement are SRGs according to ^88eu0u.

The restricted eigenvalues are the roots of

$$x^2+(\mu -\lambda )x+(\mu -k)=0.$$

If $\Gamma$ is an SRG with parameters $(v,k,\lambda ,\mu )$ and restricted eigenvalues $r,s$, then $\overline{\Gamma }$ is an SRG with parameters $(v,\overline{k},\overline{\lambda },\overline{\mu })$, restricted eigenvalues $\overline{r}$, $\overline{s}$, where

• $\overline{k}=v-k-1$
• $\overline{\lambda }=v-2k+\mu -2$
• $\overline{\mu }=v-2k+\lambda$
• $\overline{r}=-1-s$
• $\overline{s}=-1-r$, as $\overline{A}=J-I-A$.

If $\sim$ or $\nsim$ is a non-trivial equivalence relation, then $\Gamma$ is called imprimitive. That is,

• $\lambda =k-1$ or $\mu =k$
• $⟺$ $\mu =0$ or $v=2k-\lambda$
• $⟺$ $s=-1,r=k$ or $r=0,s=-k-1$
• $⟺$ either disjoint union of complete graphs, or uniform multipartite graph.

Then Primitive SRGs satisfies

• $0⩽\lambda <k-1$
• $0<\mu <k$
• $r>0$, $s<-1$, $k>r$.

Assume that the multiplicities of $r$ and $s$ are $f$ and $g$, respectively. Then we have $v=1+f+g$ and $0=\mathrm{tr}A=k+fr+gs$. It follows that

$$f=\frac{(s+1)k(k-s)}{\mu (s-r)},g=\frac{(r+1)k(k-r)}{\mu (r-s)}\in {\mathbb{Z}}^{+}.$$

Recall that $r+s=\lambda -\mu$ and $fr+gs=-k$.

• If $f\ne g$, then we can solve for $r,s$ and $r,s$ are rationals. But $r,s$ are also algebraic integers, so $r,s$ are integers.
• If $f=g$, then $f=g=(v-1)/2$ and so $(v,k,\lambda ,\mu )=(4t+1,2t,t-1,t)$ for some integer $t$ and $r,s=-1\pm \sqrt{v}/2$.

Examples.

• Paley Graphs
  • $q=4t+1$ prime power
  • $V(\Gamma )={\mathbb{F}}_q$, $x\sim y$ iff $x-y$ is a nonzero square
  • parameters $(4t+1,2t,t-1,t)$
  • we saw earlier that there are $(q-1)/2=2t=k$ nonzero squares (and symmetric as $q\equiv 1(\mathrm{mod}4)$).
  • Pasted image 20260520152508.png
• Rank $3$ permutation groups
  • Not all SRGs come from groups. As an example, consider $D_5$ acting naturally on $\{0,1,\cdots ,4\}$, and we get a cycle $C_5$, which is a SRG $(5,2,0,1)$.
• Johnson Graph on Pairs
  • Let $S_n$ act naturally on $\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$.
  • There exists three orbits on pairs.
  • $v=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, $k=2(n-2)$, $\lambda =n-2$, $\mu =4$
  • When $n=5$, we get Petersen graph.
• A $2$-$(V,K,\Lambda )$ design is called quasisymmetric if for all distinct blocks $B$ and $B^{\prime }$, $|B\cap B^{\prime }|\in \{\alpha ,\beta \}$ for constants $\alpha ,\beta$ (and both occur). Here $\alpha <\beta$, and $B\sim B^{\prime }$ iff $|B\cap B^{\prime }|=\beta$.
  • In $PG(3,q)$, two lines intersect in $0$ or $1$ points, which is a $2$-$(q^3+q^2+q+1,q+1,1)$ quasisymmetric design with $\{\alpha ,\beta \}=\{0,1\}$.
  • Let $R$ be the replication number, and let $N$ be point-block incidence matrix. Then
    • $N{N}^T=(R-\Lambda )I+\Lambda J$
    • $N^{T}N=(k-\alpha )I+\alpha J+(\beta -\alpha )A$
    • $(N^{T}N{)}^2=(R-\Lambda )N^{T}N+\Lambda k^{2}J$ is a combination of $I,J,A$.
• Lines in $PG(n-1,q)/2\text{-space}$ in $V(n,q)$. $x\sim y$ iff $\dim (x\cap y)=1$. It is a SRG with
  • $v={\left[\begin{array}{c}n\\ 2\end{array}\right]}_q$
  • $k=(q+1)q(q^{n-2}-1)/(q-1)$
  • $\lambda =q^2-2+(q^{n-1}-1)/(q-1)$
  • $\mu =(q+1{)}^2$
  • in particular, $(n,q)=(5,1)$ is Petersen graph
• A Moore graph of diameter $2$ and degree $k$ is a regular graph $\mathrm{srg}(k^2+1,k,0,1)$. The known possible degrees are $k=2,3,7,57$. The corresponding examples are:

$k$	graph	parameters
$2$	pentagon $C_5$	$\mathrm{srg}(5,2,0,1)$
$3$	Petersen graph	$\mathrm{srg}(10,3,0,1)$
$7$	Hoffman—Singleton graph	$\mathrm{srg}(50,7,0,1)$
$57$	unknown	$\mathrm{srg}(3250,57,0,1)$

Existence Conditions

• ^bebz6b
• $f,g$ must be non-negative integers
• $f\ne g$, $r,s$ must be integers
• Recall, we proved a bound on ${\lambda }_2,{\lambda }_n$ for $k$-regular graphs. See ^uq6s43.
  • For SRGs, this bound was known since the 1990s
  • For regular graphs, only 2022 (3).
  • Krein conditions for strongly regular graphs:
    • $(r+1)(k+r+2rs)\le (k+r)(s+1{)}^2$,
    • $(s+1)(k+s+2rs)\le (k+s)(r+1{)}^2$.
• Absolute bound
  • $v⩽\left(\genfrac{}{}{0ex}{}{f+2}{2}\right)-1$
  • $v⩽\left(\genfrac{}{}{0ex}{}{g+2}{2}\right)-1$
  • Proof: see ^h78omb and Pasted image 20260525170634.png.