viii Preface

of eyelets. Here, a mathematical shoe consists of 2n eyelets which are the points of

intersection of two vertical lines in the plane that are one unit apart and n equally

spaced horizontal lines that are h units apart. An n-lacing of a mathematical shoe is

a closed path in the plane consisting of 2n line segments whose endpoints are the 2n

eyelets of the shoe. Furthermore, we require that given any eyelet E, at least one of

the two segments ending in it is not contained in the same column of eyelets as E.

This condition ensures that every eyelet genuinely contributes towards pulling the

two sides of the shoe together or, less formally, that a lacing doesn’t have “gaps”.

We introduce four important special classes of n-lacings. The dense n-lacings

are the n-lacings in which the shoelace zigzags back and forth between the two

columns of eyelets. The straight n-lacings are those n-lacings that contain all possi-

ble horizontal segments. The superstraight n-lacings are the straight n-lacings all of

whose nonhorizontal segments are verticals. Finally, if, when you trace an n-lacing,

you move exactly once from the top to the bottom of the shoe and once from the

bottom to the top and if you neither “backtrack” on the way down nor on the way

up, then the n-lacing is called simple.

We describe some families of n-lacings, representatives of which are actually

used for lacing real shoes and which pop up in the different characterizations that

this set of notes is all about. See the diagram on the next page for a quick visual

description of these and other important families of n-lacings and a summary of

the most important such characterizations. For example, the two most commonly

used n-lacings are the so-called crisscross and zigzag n-lacings, which are featured

on the left side of the diagram. As you can see, they both have very neat extremal

properties.

In Chapter 2, we consider one-column n-lacings. Imagine pulling really hard

on the two ends of the shoelace in one of your shoes that has been laced using a

straight lacing. Then, if the lacing does not get in the way and if your foot is narrow

enough, you will end up with the two columns of eyelets superimposed, one on top

of the other. This means that we do not have to distinguish any longer between

the two columns of eyelets and what we are dealing with is a one-column n-lacing,

that is, a lacing of just one column of n eyelets in which every eyelet gets visited

exactly once. We identify the shortest and longest one-column n-lacings and find

the numbers of such lacings. In a final section, we describe a simple method that

allows us to construct all straight n-lacings that contract to a given one-column

n-lacing. This method plays an important role in deriving the shortest and longest

straight n-lacings in subsequent chapters.

In Chapter 3, we derive one formula each for the numbers of those n-lacings

that belong to one of ten different classes of n-lacings considered by us: general,

dense, simple, straight, dense-and-simple, dense-and-straight, etc. The highlights of

this chapter are the formula for the number of n-lacings and the formula for the

number of simple n-lacings. Especially, the latter is a very striking example of a

simple mathematical object giving rise to a beautiful, yet surprisingly complicated,

formula. Also included in this chapter are complete lists of all 2-lacings, all 3-lacings,

and all simple 4-lacings.

In Chapter 4, we extend results by Halton [13] and Isaksen [16] by deriving the

shortest n-lacings in the different classes of n-lacings in which we are interested.

Highlights of this chapter are our proofs that the bowtie n-lacings are the shortest

n-lacings overall, that the crisscross n-lacings are the shortest dense n-lacings, and