A prolific construction of strongly regular graphs with the \(n\)-e. c. property (Q698603): Difference between revisions

Summary: A graph is \(n\)-e.c.\( \) (\(n\)-existentially closed) if for every pair of subsets \(U\), \(W\) of the vertex set \(V\) of the graph such that \(U\cap W=\emptyset\) and \(|U|+|W|=n\), there is a vertex \(v\in V-(U\cup W)\) such that all edges between \(v\) and \(U\) are present and no edges between \(v\) and \(W\) are present. A graph is strongly regular if it is a regular graph such that the number of vertices mutually adjacent to a pair of vertices \(v_1,v_2\in V\) depends only on whether or not \(\{v_1,v_2\}\) is an edge in the graph. The only strongly regular graphs that are known to be \(n\)-e.c.\ for large \(n\) are the Paley graphs. Recently D. G. Fon-Der-Flaass has found prolific constructions of strongly regular graphs using affine designs. He notes that some of these constructions were also studied by Wallis. By taking the affine designs to be Hadamard designs obtained from Paley tournaments, we use probabilistic methods to show that many non-isomorphic strongly regular \(n\)-e.c.\ graphs of order \((q+1)^2\) exist whenever \(q\geq 16 n^2 2^{2n}\) is a prime power such that \(q\equiv 3\;\pmod{4}\).