NMO Selection Tests for the Balkan and International Mathematical Olympiads

Without loss of generality, we may (and will) assume all vectors anchored at the origin. Assigning to each vector $\mathbf{v}=(x,y)$ in ${\mathbb{R}}^2$ the unit vector $$\mathbf{u}=\left(\frac{2x}{x^2+y^2+1},\frac{2y}{x^2+y^2+1},\frac{x^2+y^2-1}{x^2+y^2+1}\right)$$ in ${\mathbb{R}}^3$ defines a bijection between all vectors in ${\mathbb{R}}^2$ and all unit vectors in ${\mathbb{R}}^3$ different from $(0,0,1)$; its inverse sends a unit vector $\mathbf{u}=(x,y,z)\ne (0,0,1)$ to the vector $\mathbf{v}=(x/(1-z),y/(1-z))$. Clearly, the condition $$4(\mathbf{v}\cdot {\mathbf{v}}^{\prime })+(|\mathbf{v}{|}^2-1)(|{\mathbf{v}}^{\prime }{|}^2-1)<0$$ for vectors in ${\mathbb{R}}^2$ is equivalent to $\mathbf{u}\cdot {\mathbf{u}}^{\prime }<0$ for the corresponding unit vectors in ${\mathbb{R}}^3$. Now let $S=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\}$, let $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_n\}$ be the set of corresponding unit vectors in ${\mathbb{R}}^3$ and consider the graph $G$ on $n$ vertices labelled $1,2,\dots ,n$, with an edge joining vertex $i$ to vertex $j$ if and only if ${\mathbf{u}}_i\cdot {\mathbf{u}}_j<0$. Since the largest size of a set of vectors in ${\mathbb{R}}^3$ with negative mutual dot-products is $4$, it follows that $G$ is $K_5$-free. Hence, by Turán's theorem, $G$ has at most the following number of edges $$\lfloor \left(1-\frac{1}{5-1}\right)\cdot \frac{n^2}{2}\rfloor =\lfloor 3n^2/8\rfloor ,$$ the upper bound being achieved by Turán's extremal graph $T(n,5)=K_{n_1,n_2,n_3,n_4}$, where $n_1+n_2+n_3+n_4=n$ and $|n_i-n_j|\le 1$. Geometrically, this can be achieved in ${\mathbb{R}}^3$ by considering four tight bundles of $n_i$ unit vectors each, around the vectors $(1,0,0)$, $(-1,2,0)$, $(-1,-1,3)$ and $(-1,-1,-1)$, respectively. Consequently, the required maximum is $\lfloor 3n^2/8\rfloor$.

Alternatively, notice that no five vertices of the complement $\bar{G}$ of $G$ are independent, so the independence number $\alpha (\bar{G})\le 4$, and apply the Caro-Wei theorem to get $$4\ge \alpha (\bar{G})\ge \sum _{i=1}^n\frac{1}{1+\mathrm{deg}i}\ge \frac{n}{1+\frac{1}{n}{\sum }_{i=1}^n\mathrm{deg}i}=\frac{n^2}{n+2|E(\bar{G})|}.$$ Consequently, $|E(\bar{G})|\ge n(n-4)/8$, so $|E(G)|=n(n-1)/2-|E(\bar{G})|\le 3n^2/8$.