---

Claim. Let $d=2p\ge4$ be even and let $t_p(n)$ be the number of edges of the complete $p$-partite Turán graph on $n$ vertices, so that $t_p(n)=\frac{p-1}{2p}n^2+O(n)$. Theorem 1 of the paper states that for all $n>n_0(d)$

$$t_p(n)+n-p\le f_d(n)\le t_p(n)+n,$$

with equality $f_d(n)=t_p(n)+n$ whenever $2d$ divides $n$, in the notation of Problem 1085. This determines $f_d(n)$ for every even $d\ge4$ up to an additive constant, and exactly along the multiples of $2d$.

Covers. The estimate of $f_d(n)$ for every even $d\ge4$ and all large $n$, to within the additive constant $p$. The exact value for every $n$ is not claimed; Brass's result for $d=4$ and Swanepoel's for even $d\ge6$, on their own claim pages in this folder, supply it. Nothing is claimed for odd $d$ or for $d\le3$.

Depends on. No page of this wiki.

The argument. The lower bound places the points on $p$ mutually orthogonal circles of radius $1/\sqrt2$, Lenz's construction, with the $n/p$ points on each circle taken as the vertices of $n/(4p)$ squares, which adds the $n$ unit distances inside the circles to the $t_p(n)$ between them. The upper bound uses a lemma of Erdős and Simonovits, that a graph on $n$ vertices with $t_p(n)+n+1$ edges contains the complete $(p+1)$-partite graph $K_{p+1}(1,3,\dots,3)$, together with the geometric fact that $p$ mutually orthogonal planes cannot all be at unit distance from a further point in $\mathbb R^{2p}$. The library's [[../library/distance_problems/erdos_1967_applications_graph_theory_geometry/_index|card for the paper]] records the theorem and the lemma.

Acceptance. Refereed: P. Erdős, On some applications of graph theory to geometry, Canadian Journal of Mathematics 19 (1967), 968–971. Not reviewed: the site's remarks say that this paper determined $f_d(n)$ up to $O(1)$ for all even $d\ge4$, but the site labels the problem OPEN, so the remark is not an acceptance of the problem or of a part.