Pat Morin
I will describe research that started when Sander Verdonschot told me that, in his experiments on random point sets, the θ6 graph had 25% more edges than the θ5 graph. Intuition suggests that θ6 should have 6/5-1=20% more edges.
In order to understand this discrepancy we derive exact bounds on dk, the average degree of a vertex in the θk graph of points that obey a Poisson distribution over R2. We then show that this result carries over (with small error terms) to a set of n points uniformly distributed in a square, so that the expected number of edges in such a graph is ½dkn±o(n). We also show that, in the same setting, the number of edges in the θk graph is highly concentrated around its expected value.