Approximately Strongly Regular Graphs

2022/05/11 by Ferdinand Ihringer, Ihringer, Ferdinand · 3 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2205.05792

openalex publication_date 2022/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 PG(n, q) for which the number of secants on exterior points does not vary too much, have size at most O(q^{\frac34 n}) (as q → ∞ or as n → ∞). (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 ≤ m-3 is similar to a strongly regular graph, have k = O(v^{1 - (1)/(3m-2i-5)}).

Cited by

• The non-existence of some Moore polygons and spectral Moore bounds
• From small eigenvalues to large cuts, and Chowla's cosine problem
• An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

Related

• Some Properties of Strongly Regular Graphs
• On highly regular strongly regular graphs
• An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs
• There is no strongly regular graph with parameters (460,153,32,60)
• On the extreme complexity of certain nearly regular graphs