An extremal problem motivated by triangle-free strongly regular graphs.

We introduce the following combinatorial problem. Let G be a triangle-free regular graph with edge density ρ. (In this paper all densities are normalized by n , n 2 2 etc. rather than by n − 1 , ( n 2 ) , ...) What is the minimum value a (ρ) for which there always exist two non-adjacent vertices such that the density of their common neighbourhood is ≤ a (ρ) ? We prove a variety of upper bounds on the function a (ρ) that are tight for the values ρ = 2 / 5 , 5 / 16 , 3 / 10 , 11 / 50 , with C 5 , Clebsch, Petersen and Higman-Sims being respective extremal configurations. Our proofs are entirely combinatorial and are largely based on counting densities in the style of flag algebras. For small values of ρ , our bound attaches a combinatorial meaning to so-called Krein conditions that might be interesting in its own right. We also prove that for any ϵ > 0 there are only finitely many values of ρ with a (ρ) ≥ ϵ but this finiteness result is somewhat purely existential (the bound is double exponential in 1 / ϵ). [ABSTRACT FROM AUTHOR]