Editing Strongly regular graph (section)

==Algebraic properties of strongly regular graphs==

===Basic relationship between parameters===
The four parameters in an srg(''v'', ''k'', λ, μ) are not independent: In order for an srg(''v'', ''k'', λ, μ) to exist, the parameters must obey the following relation:
:<math>(v - k - 1)\mu = k(k - \lambda - 1)</math>

The above relation is derived through a counting argument as follows:
# Imagine the vertices of the graph to lie in three levels. Pick any vertex as the root, in Level 0. Then its ''k'' neighbors lie in Level 1, and all other vertices lie in Level 2.
# Vertices in Level 1 are directly connected to the root, hence they must have λ other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each vertex has degree ''k'', there are <math>k - \lambda - 1</math> edges remaining for each Level 1 node to connect to vertices in Level 2. Therefore, there are <math>k (k - \lambda - 1)</math> edges between Level 1 and Level 2.
# Vertices in Level 2 are not directly connected to the root, hence they must have μ common neighbors with the root, and these common neighbors must all be in Level 1. There are <math>(v - k - 1)</math> vertices in Level 2, and each is connected to μ vertices in Level 1. Therefore the number of edges between Level 1 and Level 2 is <math>(v - k - 1)\mu</math>.
# Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.

This relation is a [[necessary condition]] for the existence of a strongly regular graph, but not a [[sufficient condition]]. For instance, the quadruple (21,10,4,5) obeys this relation, but there does not exist a strongly regular graph with these parameters.<ref>{{citation
 | last1 = Brouwer | first1 = A. E.
 | last2 = van Lint | first2 = J. H.
 | contribution = Strongly regular graphs and partial geometries
 | contribution-url = https://pure.tue.nl/ws/portalfiles/portal/2394798/595248.pdf
 | isbn = 0-12-379120-0
 | mr = 782310
 | pages = 85–122
 | publisher = Academic Press, Toronto, ON
 | title = Enumeration and design (Waterloo, Ont., 1982)
 | year = 1984}}</ref>

===Adjacency matrix equations===
Let ''I'' denote the [[identity matrix]] and let ''J'' denote the [[matrix of ones]], both matrices of order ''v''.  The [[adjacency matrix]] ''A'' of a strongly regular graph satisfies two equations.

First:
:<math>AJ = JA = kJ,</math>
which is a restatement of the regularity requirement. This shows that ''k'' is an eigenvalue of the adjacency matrix with the all-ones eigenvector.

Second:
:<math>A^2 = kI + \lambda{A} + \mu(J - I - A)</math>
which expresses strong regularity. The ''ij''-th element of the left hand side gives the number of two-step paths from ''i'' to ''j''. The first term of the right hand side gives the number of two-step paths from ''i'' back to ''i'', namely ''k'' edges out and back in. The second term gives the number of two-step paths when ''i'' and ''j'' are directly connected. The third term gives the corresponding value when ''i'' and ''j'' are not connected. Since the three cases are [[mutually exclusive]] and [[collectively exhaustive]], the simple additive equality follows.

Conversely, a graph whose adjacency matrix satisfies both of the above conditions and which is not a complete or null graph is a strongly regular graph.<ref>{{citation|first1=P.J.|last1=Cameron|first2=J.H.|last2=van Lint|title=Designs, Graphs, Codes and their Links|publisher=Cambridge University Press|series=London Mathematical Society Student Texts 22|year=1991|isbn=978-0-521-42385-4|page=[https://archive.org/details/designsgraphscod0000came/page/37 37]|url=https://archive.org/details/designsgraphscod0000came/page/37}}</ref>

===Eigenvalues and graph spectrum===
Since the adjacency matrix A is symmetric, it follows that [[orthogonal basis|its eigenvectors are orthogonal]]. We already observed one eigenvector above which is made of all ones, corresponding to the eigenvalue ''k''. Therefore the other eigenvectors ''x'' must all satisfy <math>Jx = 0</math> where ''J'' is the all-ones matrix as before. Take the previously established equation:
:<math>A^2 = kI + \lambda{A} + \mu(J - I - A)</math>
and multiply the above equation by eigenvector ''x'':
:<math>A^2 x = kIx + \lambda{A}x + \mu(J - I - A)x</math>
Call the corresponding eigenvalue ''p'' (not to be confused with <math>\lambda</math> the graph parameter) and substitute <math>Ax = px</math>, <math>Jx = 0</math> and <math>Ix = x</math>:
:<math>p^2 x = kx + \lambda p x - \mu x - \mu p x</math>
Eliminate x and rearrange to get a quadratic:
:<math>p^2 + (\mu - \lambda ) p - (k - \mu) = 0</math>

This gives the two additional eigenvalues <math>\frac{1}{2}\left[(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]</math>. There are thus exactly three eigenvalues for a strongly regular matrix.

Conversely, a connected regular graph with only three eigenvalues is strongly regular.<ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag, New York, 2001, Lemma 10.2.1.</ref>

Following the terminology in much of the strongly regular graph literature, the larger eigenvalue is called ''r'' with multiplicity ''f'' and the smaller one is called ''s'' with multiplicity ''g''.

Since the sum of all the eigenvalues is the [[Trace (linear algebra)|trace of the adjacency matrix]], which is zero in this case, the respective multiplicities ''f'' and ''g'' can be calculated:
* Eigenvalue ''k'' has [[Multiplicity (mathematics)|multiplicity]] 1.
* Eigenvalue <math>r = \frac{1}{2}\left[(\lambda - \mu) + \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]</math> has multiplicity <math>f = \frac{1}{2}\left[(v - 1) - \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>
* Eigenvalue <math>s = \frac{1}{2}\left[(\lambda - \mu) - \sqrt{(\lambda - \mu)^2 + 4(k-\mu)}\,\right]</math> has multiplicity <math>g = \frac{1}{2}\left[(v - 1) + \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>

As the multiplicities must be integers, their expressions provide further constraints on the values of ''v'', ''k'', ''μ'', and ''λ''.

Strongly regular graphs for which <math>2k + (v - 1)(\lambda - \mu) \ne 0</math> have integer eigenvalues with unequal multiplicities.

Strongly regular graphs for which <math>2k + (v - 1)(\lambda - \mu) = 0</math> are called [[conference graph]]s because of their connection with symmetric [[conference matrix|conference matrices]]. Their parameters reduce to
: <math>\operatorname{srg}\left(v, \frac{1}{2}(v - 1), \frac{1}{4}(v - 5), \frac{1}{4}(v - 1)\right).</math>
Their eigenvalues are <math>r =\frac{-1 + \sqrt{v}}{2}</math> and <math>s = \frac{-1 - \sqrt{v}}{2}</math>, both of whose multiplicities are equal to <math>\frac{v-1}{2}</math>. Further, in this case, ''v'' must equal the sum of two squares, related to the [[Bruck–Ryser–Chowla theorem]].

Further properties of the eigenvalues and their multiplicities are:<ref>Brouwer & van Meldeghem, ibid.</ref>
* <math>(A - rI)\times(A - sI) = \mu.J</math>, therefore <math>(k - r).(k - s) = \mu v</math>
* <math>\lambda - \mu = r + s</math>
* <math>k - \mu = -r\times s</math>
* <math>k \ge r</math>
* Given an {{nowrap|srg(''v'', ''k'', λ, μ)}} with eigenvalues ''r'' and ''s'', its complement {{nowrap|srg(''v'', ''v'' − ''k'' − 1, ''v'' − 2 − 2''k'' + μ, ''v'' − 2''k'' + λ)}} has eigenvalues ''-1-s'' and ''-1-r''.
* Alternate equations for the multiplicities are <math>f =\frac{(s+1)k(k-s)}{\mu(s-r)}</math> and <math>g =\frac{(r+1)k(k-r)}{\mu(r-s)}</math>
* The frame quotient condition: <math>v k (v-k-1) = f g (r-s)^2</math>. As a corollary, <math>v = (r-s)^2</math> [[if and only if]] <math>{f,g} = {k, v-k-1}</math> in some order.
* Krein conditions: <math>(v-k-1)^2 (k^2 + r^3) \ge (r+1)^3 k^2</math> and <math>(v-k-1)^2 (k^2 + s^3) \ge (s+1)^3 k^2</math>
* Absolute bound: <math>v \le \frac{f(f+3)}{2}</math> and <math>v \le \frac{g(g+3)}{2}</math>.
* Claw bound: if <math>r + 1 > \frac{s(s+1)(\mu+1)}{2}</math>, then <math>\mu = s^2</math> or <math>\mu = s(s+1)</math>.
If any of the above conditions are violated for a set of parameters, then there exists no strongly regular graph for those parameters. Brouwer has compiled such lists of existence or non-existence [https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html here] with reasons for non-existence if any. For example, there exists no srg(28,9,0,4) because that violates one of the Krein conditions and one of the absolute bound conditions.

===The Hoffman–Singleton theorem===
As noted above, the multiplicities of the eigenvalues are given by 
:<math>M_{\pm} = \frac{1}{2}\left[(v - 1) \pm \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>
which must be integers.

In 1960, [[Alan J. Hoffman|Alan Hoffman]] and Robert Singleton examined those expressions when applied on [[Moore graph]]s that have ''λ'' = 0 and ''μ'' = 1. Such graphs are free of triangles (otherwise ''λ'' would exceed zero) and quadrilaterals (otherwise ''μ'' would exceed 1), hence they have a girth (smallest cycle length) of 5. Substituting the values of ''λ'' and ''μ'' in the equation <math>(v - k - 1)\mu = k(k - \lambda - 1)</math>, it can be seen that <math>v = k^2 + 1</math>, and the eigenvalue multiplicities reduce to
:<math>M_{\pm} = \frac{1}{2}\left[k^2 \pm \frac{2k - k^2}{\sqrt{4k - 3}}\right]</math>

For the multiplicities to be integers, the quantity <math>\frac{2k - k^2}{\sqrt{4k - 3}}</math> must be rational, therefore either the numerator <math>2k - k^2</math> is zero or the denominator <math>\sqrt{4k - 3}</math> is an integer.

If the numerator <math>2k - k^2</math> is zero, the possibilities are:
* ''k'' = 0 and ''v'' = 1 yields a trivial graph with one vertex and no edges, and 
* ''k'' = 2 and ''v'' = 5 yields the 5-vertex [[cycle graph]] <math>C_5</math>, usually drawn as a [[regular pentagon]].

If the denominator <math>\sqrt{4k - 3}</math> is an integer ''t'', then <math>4k - 3</math> is a perfect square <math>t^2</math>, so <math>k = \frac{t^2 + 3}{4}</math>. Substituting:

:<math>\begin{align}
M_{\pm} &= \frac{1}{2} \left[\left(\frac{t^2 + 3}{4}\right)^2 \pm \frac{\frac{t^2 + 3}{2} - \left(\frac{t^2 + 3}{4}\right)^2}{t}\right] \\
32 M_{\pm} &= (t^2 + 3)^2 \pm \frac{8(t^2 + 3) - (t^2 + 3)^2}{t} \\
 &= t^4 + 6t^2 + 9 \pm \frac{- t^4 + 2t^2 + 15}{t} \\
 &= t^4 + 6t^2 + 9 \pm \left(-t^3 + 2t + \frac{15}{t}\right)
\end{align}</math>

Since both sides are integers, <math>\frac{15}{t}</math> must be an integer, therefore ''t'' is a factor of 15, namely <math>t \in \{\pm 1, \pm 3, \pm 5, \pm 15\}</math>, therefore <math>k \in \{1, 3, 7, 57\}</math>. In turn:
* ''k'' = 1 and ''v'' = 2 yields a trivial graph of two vertices joined by an edge,
* ''k'' = 3 and ''v'' = 10 yields the [[Petersen graph]],
* ''k'' = 7 and ''v'' = 50 yields the [[Hoffman–Singleton graph]], discovered by Hoffman and Singleton in the course of this analysis, and
* ''k'' = 57 and ''v'' = 3250 predicts a famous graph that has neither been discovered since 1960, nor has its existence been disproven.<ref>{{citation
 | last = Dalfó | first = C.
 | doi = 10.1016/j.laa.2018.12.035
 | journal = Linear Algebra and Its Applications
 | mr = 3901732
 | pages = 1–14
 | title = A survey on the missing Moore graph
 | volume = 569
 | year = 2019 | hdl = 2117/127212
 | s2cid = 126689579
 | hdl-access = free
}}</ref>

The Hoffman-Singleton theorem states that there are no strongly regular girth-5 Moore graphs except the ones listed above.