Longest induced cycles in random geometric graphs near criticality

Question

We make a random geometric graph $X(n;r)$ as follows. Choose $n$ points uniformly, independently, in the unit square $[0,1]^2$, for vertices, and then connect a pair of vertices $\{ p,q \}$ by an edge if $d(p,q) < r$. For the purposes of this question, we set $r = c / \sqrt{n}$, where $c>0$ is small.

It is known (see for example Mathew Penrose's book Random Geometric Graphs) that as $n \to \infty$, with probability approaching one, there are no connected components on more than $O( \log n)$ vertices. That is, as long as $c$ is sufficiently small, we are in the sub-critical regime in the sense of continuum percolation.

What I'd like to know is a good upper bound for the number of vertices in the longest induced cycle in $X(n;r)$. By the above we know that, with high probability, there are no induced cycles on more than $O( \log n)$ vertices, but this seems like a fairly coarse bound and I would like to know if it possible to improve this to something like $O( \sqrt{ \log n} )$. (I know that it is not possible to get much smaller than $O( \sqrt{ \log n} )$; with high probability, there are induced cycles that are about this long.)

[Penrose's book covers in great detail: subgraph counts, induced subgraph counts etc., but in the case when the size of the subgraph is fixed, so this is a different sort of problem.]

Answer 1

There are induced cycles of length $ \Omega( \log n ) $ for the regime when $r = c/\sqrt{n}$ with $c>0$ a constant. Therefore, the length of the longest induced cycle is $\Theta( \log n )$ if $c$ is such that we are still in the subcritical regime, since as you mention the largest component is known to be of size $O(\log n)$ here.

(A sketch of) an argument would go as follows. First off, it is convenient to Poissonize, i.e. instead of exactly $n$ points we drop $\text{Poisson}(n)$ points. It is easy couple the two models such that the probability that there is an induced cycle on length $\Theta(\log n )$ in one but not the other is $o(1)$.

Place squares of side say $\frac{r}{100}$ in two horizontal rows of each $d \log n$ squares, where $d>0$ is a small constant that will depend on $c$ and that we will specify later on, such that if points are placed inside these boxes, each point will be adjacent to the points in the preceding and next box in the same row but not to the points inside boxes in the other row. Having chosen the vertical distance correctly, we can place two more boxes, one halfway between the leftmost boxes of the two rows and one between the rightmost boxes of the two rows such that if points fall inside these two boxes then these will be adjacent to the points in the boxes immediately above and below them but no points in the other boxes. See the picture below.

Note that, if each of the squares contains exactly one point then you have an induced cycle of the desired length $\Omega( \log n )$.

For each square the number of points that falls inside is Poisson distributed with mean $\frac{nr^2}{10^4} = \frac{c^2}{10^4}$. Thus the probability that exactly one points falls inside a box is a constant $f = f(c)$ that depends on $c$ only. (To be precise $f= c^2 10^{-4} e^{-c^2 10^{-4}}$.)

The probability that each of the boxes contains exacty one point is thus $$f^{2 d \log n + 2} = \Omega( n^{2 d \log f} ) $$ (using that the point counts in different boxes are independent since we are dealing with a Poisson process.)

Having chosen $d$ correctly in the beginning, we can assume that $2 d\log f > -1/2$, say.

Now we note that we can place $\Omega(\frac{n}{\log n} )$ non-overlapping copies of this construction in the unit square. (To see this, note the construction lives inside a rectangle of dimensions $\Theta(\log n \cdot r) \times \Theta(r)$.)

Hence the expected number of constructions in which we "succeed" is $$ \Omega\left( \frac{n}{\log n} \cdot f^{2 d \log n + 2} \right) = \Omega( n^{1/2+o(1)} ). $$ The number of constructions that succeed is binomially distributed (again using that we're dealing with a Poisson process). So, standard bounds (e.g. the Chernoff bound) will show that, with probability $1-o(1)$, at least one of the constructions succeeds.