Approximately Strongly Regular Graphs

DOI10.1016/J.DISC.2022.113299MaRDI QIDQ6398942arXivFDO

Authors Ferdinand Ihringer

Publication date 11 May 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.113299

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Extremal problems in graph theory (05C35) Association schemes, strongly regular graphs (05E30) Linear codes and caps in Galois spaces (51E22)

arXiv classification

math.CO

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 $mathrmPG(n,q)$ for which the number of secants on exterior points does not vary too much, have size at most $O(q^{frac34n})$ (as $qightarrowinfty$ or as $nightarrowinfty$). (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 $ileqm-3$ is similar to a strongly regular graph, have $k=O(v^{1-frac13m-2i-5})$.

This page was built for publication: Approximately Strongly Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398942)