Circle grids and bipartite graphs of distances (Q1894698)

Given two point sets \(A\) and \(B\) of size \(n\) and \(t\), respectively, let \(f_t (n)\) be the minimum number of distinct distances realized by one point of each set. If \(t \geq 2\), then \(f_t(n) \geq \lceil \sqrt {n/2} \rceil\). If \(t \geq 3\) and \(n \geq 4t^3\), it is shown that \(f_t (n) \leq \sqrt {nt} + 3t/2\). The latter bound is new and follows by a construction that uses circular grids. A second result of the paper concerns largest distances. Given a set \(A\) of \(n\) points, let \(G\) be the graph with arcs between nodes (the points) for the \(k\) largest different distances between two points of \(A\) (so \(G\) may have many more than \(k\) arcs). Given integers \(t\) and \(k\) let \(g_t (k)\) be the maximum value for \(n\) such that a point set \(A\) exists with \(K_{t,n} \subset G\). It is shown that for \(t \geq 3\) and \(k \geq 2t^2\) we have \(g_t (k) \geq (k - 2t)^2/(2t)\).