Circle grids and bipartite graphs of distances
type: Item
instance of: scholarly article
title: Circle grids and bipartite graphs of distances
zbMATH Open document ID: 0827.52010
DOI: 10.1007/BF01200753
published in: Combinatorica
publication date: 1995-12-11T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 778331
zbMATH Keywords: geometric graphs
zbMATH Keywords: point sets
zbMATH Keywords: distances
author: György Elekes
MaRDI profile type: Publication
cites work: n points in the plane can determine \(n^{3/2}\) unit circles
cites work: On the graph of large distances
full work available at URL: https://doi.org/10.1007/bf01200753
OpenAlex ID: W2043987727
description: scientific article; zbMATH DE number 778331