Erdős Problem #133

Let \(f(n)\) be minimal such that every triangle-free graph \(G\) with \(n\) vertices and diameter \(2\) contains a vertex with degree \(\geq f(n)\). What is the order of growth of \(f(n)\)? Does \(f(n)/\sqrt{n}\to \infty\)? Asked by Erdős and Pach. The lower bound \(f(n)\geq (1-o(1))\sqrt{n}\) follows from the fact that a graph with maximum degree \(d\) and diameter \(2\) has at most \(1+d+d(d-1)=d^2+1\) many vertices. Hanson and Seyffarth [HaSe84] proved that \(f(n)\leq (\sqrt{2}+o(1))\sqrt{n}\) using a Cayley graph on \(\mathbb{Z}/n\mathbb{Z}\), with the generating set given by some symmetric complete sum-free set of size \(\sim \sqrt{n}\). An alternative construction of such a complete sum-free set was given by Haviv and Levy [HaLe18]. Füredi and Seress [FuSe94] proved that \(f(n)\leq (\frac{2}{\sqrt{3}}+o(1))\sqrt{n}\). In particular \(f(n)/\sqrt{n}\not\to\infty\). The precise asymptotics of \(f(n)\) are unknown; Alon believes that the truth is \(f(n)\sim \sqrt{n}\).