An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs

Abstract

We introduce the following combinatorial problem. Let $G$ be a triangle-free regular graph with edge density $\rho$. What is the minimum value $a(\rho )$ for which there always exist two non-adjacent vertices such that the density of their common neighborhood is $\le a(\rho )$? We prove a variety of upper bounds on the function $a(\rho )$ that are tight for the values $\rho =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 $\rho$, our bound attaches a combinatorial meaning to Krein conditions that might be interesting in its own right. We also prove that for any $\epsilon >0$ there are only finitely many values of $\rho$ with $a(\rho )\ge \epsilon$ but this finiteness result is somewhat purely existential (the bound is double exponential in $1/\epsilon$).

34 pages, 3 figures