Approximately Strongly Regular Graphs

Abstract

We give variants of the Krein bound and the absolute bound for graphs with a spectrum similar to that of a strongly regular graph. In particular, we investigate what we call approximately strongly regular graphs. We apply our results to extremal problems. Among other things, we show the following: (1) Caps in $\mathrm{PG}(n,q)$ for which the number of secants on exterior points does not vary too much, have size at most $O(q^{\frac{3}{4}n})$ (as $q\to \infty$ or as $n\to \infty$). (2) Optimally pseudorandom $K_m$-free graphs of order $v$ and degree $k$ for which the induced subgraph on the common neighborhood of a clique of size $i\le m-3$ is similar to a strongly regular graph, have $k=O(v^{1-\frac{1}{3m-2i-5}})$.

arXiv comment24 pages; most material from version 1 is back, more examples, inertia bound added