Spreads in strongly regular graphs (Q677166): Difference between revisions

A spread in any geometry is a set of pairwise disjoint lines that cover all the points. For a partial geometry the point graph (collinearity graph) is strongly regular. Delsarte showed that a clique in a strongly regular graph has at most \(K = 1 - k/s\) vertices, where \(k\) and \(s\) are the largest and smallest eigenvalues of the graph respectively. The lines of a partial geometry are cliques in the point graph which meet this bound. This leads to the natural definition of a spread of a strongly regular graph as a partition of the vertex set into cliques that meet Delsarte's bound. Thus, a spread of a partial geometry provides a spread of its point graph. Hoffman proved that the chromatic number of a graph \(\Gamma\) is at least \(K\), and any coloring meeting this bound is called a Hoffman-coloring. Each color class of a Hoffman-coloring of \(\Gamma\) is a coclique of size meeting the Delsarte bound of the complement of \(\Gamma\), thus, a Hoffman-coloring of a strongly regular graph \(\Gamma\) is equivalent to a spread of the complement of \(\Gamma\) (also strongly regular). This paper is mostly concerned with the existence problem for strongly regular graphs with spreads and/or Hoffman-colorings. Various partial geometries, three-class association schemes, and linked symmetric designs are examined for properties that would lead to examples or non-existence results. A list of feasible parameter sets for strongly regular graphs with a spread on 100 or fewer vertices is provided together with the known information on existence. Also, the McLaughlin graph (on 275 vertices) is shown to possess a spread. The graph and spread (obtained by a computer search) are explicitly given. For strongly regular graphs related to regular two-graphs, spreads give lower bounds for the number of non-isomorphic strongly regular graphs in the switching class of the regular two-graph.