12
$\begingroup$

I wonder if anyone has counted these curves, either exactly or asymptotically?

Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$ lattice points: a lattice square. Define a rectilinear filler curve for $S_n$ to be a simple closed curve that passes through each of the $n^2$ lattice points, and is composed entirely of vertical and horizontal edges. So the curve is what is called a "rectilinear" or "orthogonal" polygon in the literature. Every turn of such a curve is $\pm 90^\circ$.

I'd like to know the number $f(n)$ of distinct filler curves for $S_n$, distinct up to rotations and reflections. So if $C_1$ can be rotated and/or reflected to lay on top of $C_2$, then $C_1$ and $C_2$ are not distinct.

$f(2) = 1$, and $f(4) = 2$:


          Filler4x4


$f(n)=0$ when $n$ is odd, as can be seen as follows. View a filler curve $C$ as composed of unit-length segments connecting lattice points; call these the edges of $C$ (so two incident edges can be collinear). Each horizontal line $y = m + \frac{1}{2}$ for $m$ an integer crosses an even number of edges of $C$; similarly for vertical lines. So the total number of edges $E$ of $C$ is even. In Euler's relation $V-E+F=2$, $F=2$ (interior & exterior of $C$). So $V=E$. So $V$ must be even. But $V=n^2$ for $n$ odd is odd.

Already I don't know what is $f(6)$. It is easy to see the growth of $f$ is exponential in $n$, but I don't know more. In particular, I do not see how to recursively connect $f(n)$ to $f(n-2)$.


          FIller6x6


$\endgroup$
8
  • 1
    $\begingroup$ See "UST =(Uniform Spanning Tree) Peano Curve": youtube.com/watch?v=4RQmLNa5ZNo $\endgroup$ Jul 25, 2018 at 10:59
  • $\begingroup$ These are studied in the context of Schramm-Loewner evolution (SLE). See e.g. Figure 9.2 of annals.math.princeton.edu/wp-content/uploads/…. The point is that SLE has three qualitative regimes based on its parameter $\kappa$. The last regime, with $\kappa/geq 8$, is where it is a space-filling curve. These discrete Peano curves are conjectured (I believe it is still a conjecture) to limit to SLE with $\kappa=8$. $\endgroup$ Jul 25, 2018 at 11:01
  • 1
    $\begingroup$ But in terms of counting these, I believe it amounts to counting spanning trees on a grid (which I think should be known). This is because these curves "go between" a tree and dual tree. See pages 8-9 of arxiv.org/pdf/math/0112234.pdf for more details. $\endgroup$ Jul 25, 2018 at 11:05
  • 1
    $\begingroup$ These are Hamiltonian cycles on the $2n \times 2n$ square grid. Their numbers are tabulated as oeis.org/A003763. The asymptotics should be known to people dealing with self-awoiding walks (SAW). $\endgroup$ Jul 25, 2018 at 12:03
  • 4
    $\begingroup$ By the way, a simpler argument for showing that there are no Hamiltonian cycles in the odd case is by coloring vertices black and white in chessboard manner and noting that the colors alternate along the cycle. Or, in other words, a bipartite graph with parts of different sizes is not Hamiltonian. $\endgroup$ Jul 25, 2018 at 12:05

2 Answers 2

8
$\begingroup$

The asymptotics of the number of Hamiltonian paths from one corner to the opposite (they exist only for $n$ odd) is $\tau^{n^2}$, where $\tau$ is not known exactly but satisfies $1.429 < \tau < 1.530$:

Bousquet-Mélou, M.; Guttmann, A. J.; Jensen, I., Self-avoiding walks crossing a square, J. Phys. A, Math. Gen. 38, No. 42, 9159-9181 (2005). ZBL1078.82009.

One can transform a path or cycle on $n \times n$ grid into a cycle or path on $(n+1) \times (n+1)$ grid, see figure. It follows that the number of cycles on $n \times n$ grid is between $\tau^{(n-1)^2}$ and $\tau^{(n+1)^2}$, and in any case between $1.429^{n^2}$ and $1.53^{n^2}$.

enter image description here

Wikipedia knows more about self-avoiding walks.

$\endgroup$
10
  • $\begingroup$ Thank you, Ivan! Mod'ing out the rotations and reflections might not be easy, but your answer and the OEIS entry you cited bring me close enough. $\endgroup$ Jul 25, 2018 at 20:49
  • 3
    $\begingroup$ Oh, I have overlooked that you are counting up to symmetries. Asymptotically it changes nothing. And an algorithm for computation (as well as values for small $n$) can be found in arxiv.org/abs/1402.0545. $\endgroup$ Jul 26, 2018 at 17:45
  • $\begingroup$ Oh, perfect!: "Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs." Ed Wynn. I think his results imply $f(6)=28$, but this needs further study. $\endgroup$ Jul 26, 2018 at 22:32
  • $\begingroup$ See @AndrásSalamon's correction: $f(6)=149$. $\endgroup$ Jul 31, 2018 at 15:46
  • $\begingroup$ I agree with András's correction -- and oeis.org/A209077 credits Jon Wild for finding the 149 solutions in 2011. $\endgroup$
    – Ed Wynn
    Sep 13, 2018 at 13:13
3
$\begingroup$

This is a summary of the sprawling comments above.

This is OEIS sequence http://oeis.org/A209077 (number of isomorphism classes of Hamiltonian circuits on $2n \times 2n$ grid). Ed Wynn discussed a method of computing these in https://arxiv.org/abs/1402.0545 and extended the known values from $1 \le n \le 4$ to $1 \le n \le 10$.

In particular, for the 6 by 6 grid (where $n=3$) which was asked about in the question, there are 149 of these circuits up to reflections and rotations.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.