cp's OEIS Frontend

A347941 For sets of n random points in the real plane, a(n) is an upper bound for the minimal number of nearest neighbors.

%I A347941 #23 Nov 01 2021 01:18:15
%S A347941 2,2,2,2,2,2,2,2,3,3,3,4,4,4,4,4,4,5,5,5,6,6,6,6,6,6,7,7,7,8,8,8,8,8,
%T A347941 8,9,9,9,10,10,10,10,10,10,11,11,11,12,12,12,12,12,12,13,13,13,14,14,
%U A347941 14,14,14,14,15,15,15,16,16,16,16,16,16,17,17,17,18,18,18,18,18,18,19,19,19,20,20,20,20,20,20,21,21,21,22,22,22,22,22,22,23
%N A347941 For sets of n random points in the real plane, a(n) is an upper bound for the minimal number of nearest neighbors.
%C A347941 The sequence deals with sets of n points with pairwise different distances. The randomness in the definition provides for pairwise different distances with probability = 1.
%C A347941 A point A is called a nearest neighbor if there is a point B with smaller distance to A than to any other point C.
%C A347941 In graph theory terms: Let G be a simple digraph; the vertices of G are n arbitrarily placed points in R^2 with pairwise different distances; the edges of G are arrows joining each point (tail end) to its nearest neighbor (head end). Let b(n) be the minimal number of points receiving arrowheads in any such graph. a(n) is the best upper bound yet known for b(n).
%C A347941 A261953(n) for n >= 2 can be seen as an "inverse" to a(n).
%C A347941 a(n) is built by constructing G with n points and m nearest neighbors, m chosen as minimal as possible, then defining a(n)=m.
%C A347941 The start is a(n)=2 for n <= 9 and a(n)=3 for n=10,11,12. We call the pairs (n,m)=(9,2) and (n,m)=(12,3) "anchor pairs" and proceed to bigger n by combining graphs with these anchor pairs to bigger graphs. So the next anchor pairs are (18,4), (21,5) and (27,6).
%C A347941 If (n0,m-1) and (n1,m) are anchor pairs then a(n')=m for n0 < n' <= n1.
%C A347941 We conjecture that a(n) is optimal. This claim is true if the following assumptions hold:
%C A347941 - The anchor pairs (9,2) and (12,3) are optimal.
%C A347941 - All bigger anchor pairs (n,m) are constructed by combining copies of (9,2) if m is even and adding one (12,3) if m is odd.
%H A347941 Manfred Boergens, <a href="https://github.com/maboerg/Next-neighbours">Next-neighbours</a>
%H A347941 <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,0,0,0,1,-1).
%F A347941 a(2) = a(3) = 2.
%F A347941 a(n) = 2j for n = 9j-5 ... 9j, j > 0;
%F A347941 a(n) = 2j+1 for n = 9j+1 ... 9j+3, j > 0;
%F A347941 With h=(n+5)/9 for n>3:
%F A347941 a(n) = 2*floor(h) if h-floor(h)<2/3;
%F A347941 a(n) = 2*floor(h)+1 otherwise.
%F A347941 G.f.: -x^2*(x^11-2*x^9+x^8+2)/(-x^10+x^9+x-1). - _Alois P. Heinz_, Sep 20 2021
%e A347941 G with 25 vertices has at least 6 nearest neighbors (conjectured; it is proved that there are G with n=25 and m=6 but it is not yet proved that 6 is the minimum).
%t A347941 h=(n+5)/9; Join[{2,2}, Table[2 Floor[h] + If[FractionalPart[h]<2/3, 0, 1], {n, 4, 100}]]
%Y A347941 Cf. A261953.
%K A347941 nonn,easy
%O A347941 2,1
%A A347941 _Manfred Boergens_, Sep 20 2021