Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time $\tau \left(G_N\right)$ of a planar graph $G_N$ of $N$ vertices and maximal degree $d$ is lower bounded by $\tau \left(G_N\right)⩾C_{d}N{\left(\ln N\right)}^2$ with $C_d=(d/4\pi )\tan (\pi /d)$, with equality holding for some geometries. We tested this conjecture on the regular honeycomb ($d=3$), regular square ($d=4$), regular elongated triangular ($d=5$), and regular triangular ($d=6$) lattices, as well as on the nonregular Union Jack lattice ($d_{\min }=4$, $d_{\max }=8$). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

Figure 1

Planar graphs investigated in this article. From left to right we have the honeycomb ($d=3$), square ($d=4$), elongated triangular ($d=5$), triangular ($d=6$), and Union Jack ($d_{\min }=4$, $d_{\max }=8$) lattices.

Figure 2

Cover times for the planar lattices depicted in Fig. 1. Each graph displays the empirical cover times $\tau \left(G_N\right)$ (open squares, left scale) together with the conjectured value ${\tau }^{*}\left(G_N\right)=C_{d}N{\left(\ln N\right)}^2$ (solid line, left scale) and the ratio ${\tau }^{*}\left(G_N\right)/\tau \left(G_N\right)$ (full squares, right scale). Each point of the $\tau \left(G_N\right)$ curves was obtained as an average over ${10}^6$ samples. For the Union Jack lattice we display the ratio ${\tau }^{*}\left(G_N\right)/\tau \left(G_N\right)$ both for $C_d$ with $d=d_{\max }=8$ and $d=\overline{d}=\frac{1}{2}(d_{\min }+d_{\max })=6$; the plots of ${\tau }^{*}\left(G_N\right)$ for these two values of $d$ are indistinguishable on the left scale of the graph and appear as a single line passing through the open squares.

Figure 3

Histogram plot of ${10}^6$ cover times sampled for a square lattice of $N=1280\times 1280$ vertices. There are 23 bins in the histogram, with the leftmost bin centered at $70\times {10}^6$ and the righmost bin centered at $180\times {10}^6$. The vertical dashed lines indicate the empirical mean $m$ and $\pm s$ intervals. The continuous line corresponds to the adjusted beta PDF (4) with shape parameters $\alpha =5.759\pm 0.008$ and $\beta =18.04\pm 0.02$. The empirical cumulative distribution function is also shown (open squares, right scale).