Through Mazes 

to Mathematics

Where else do the maze numbers occur?
At the same time (198688) that I was investigating the maze numbers
{M(n) = number of different S.A.T. mazes with n levels}
other people in different parts of the world were thinking
about the same mathematical problem.
V. I. Arnol'd
An identical counting problem was proposed by
V. I. Arnol'd in Moscow; it is related to
his work
which appeared in the Siberian Mathematical Journal
of SeptemberOctober 1988.
Arnol'd
had defined a meander as a connected oriented
nonselfintersecting curve which intersects a fixed oriented
line in several points.
His article contains this figure which, if tilted to the right,
shows exactly the eight mazepaths of
depth 6, and his M_{5} is the maze number M(6). Arnol'd gives the
first sixteen "meandering numbers," up to
M_{16} = M(17) = 252939.
Vladimir A. Kazakov  Ivan Kostov
At approximately the same time, the calculation of M(n)
came up in another context, this time in the computation of
a matrix integral arising in quantum field theory.
I learned of this work from Alexander Zvonkin, whom I thank
for his correspondence. Later, he and Lando published an
account of this work in their 1993
paper.
Warren Smith
There was another simultaneous and completely
independent occurrence of this problem.
Warren Smith, working on a new, subexponential
traveling salesman algorithm in his 1988 Princeton
thesis
defined jt(N) as the number of topologically distinct ways
in which a Jordan curve can cross an oriented line in the plane at
exactly 2N points, and computed up to jt(10) = M(20) = 8152860.
(May 13 2013) This page has been
translated into Ukrainian by
http://coffeehealtheffects.com.
(June 23 2013) This page has been
translated into
Czech.
Return to Main Maze Page
Return to Tony's Home Page
Tony Phillips
Math Dept SUNY Stony Brook
tony at math.stonybrook.edu
March 12 1997
April 6 1999