Let $\mathcal{S}^d\_{\epsilon}$ be the collection of all sets $S:=\{\mathbf{x}\_1, \mathbf{x}\_2, \ldots \mathbf{x}\_{d+1}\}$ of $d+1$ points in a $d$-dimensional Euclidean space such that, for a given constant $\epsilon>0$, we have $\|\mathbf{x}\_i-\mathbf{x}\_j\|\_2\in[1-\epsilon,1]$ for all $i\neq j$.


Given any set $S\in\mathcal{S}^d\_{\epsilon}$, let $n(S)$ be the number of triangles whose vertices $\mathbf{x}\_i, \mathbf{x}\_j, \mathbf{x}\_k$ are points of $S$, such that $\|\mathbf{x}\_i-\mathbf{x}\_j\|\_2=\|\mathbf{x}\_j-\mathbf{x}\_k\|\_2=1$ and $\|\mathbf{x}\_k-\mathbf{x}\_i\|\_2<1$.




---


**Question:** How can we calculate (or approximate) $m(d,\epsilon):=\max\_{S\in\mathcal{S}^d\_{\epsilon}}n(S)$?



Combinatorial Euclidean geometry problem
Since any graph with $d+1$ vertices can be realized as a unit distance graph in $\mathbb{R}^d$, with remaining distances smaller than $1$ (and arbitrarily close to 1), the question is then equivalent to the maximum possible number of induced paths of length $2$ (equivalently, induced copies of $K\_{2,1}$), in a graph with $d+1$ vertices.


This is maximized for the balanced complete bipartite graph, where approximately half of the triples of vertices induce $K\_{2,1}$; see Theorem 10 in [1]:


[1] N. Pippenger and M. C. Golumbic, The inducibility of graphs, Journal of Combinatorial Theory, Series B, Volume 19, Issue 3, December 1975, Pages 189-203; <https://www.sciencedirect.com/science/article/pii/0095895675900842>


In particular, $m(d,\epsilon)$ does not depend on $\epsilon$.


