Incidences

Why do we still teach geometry?  The constructions with ruler and compass were essential for the Egyptians and Greeks in order to accurately lay out large scale buildings with the only tool available (the rope). But today we have many other tools available, so there is no reason to confine ourselves to ruler and compass, unless we want to use them as a vehicle to teach the concept of proofs. That, however, is also in low demand, to the extent that graduating majors in mathematics are neither able to prove Pythagoras’ theorem nor to compute the distance of a point from a line.

Central

I have been teaching a Geometry class twice now, and I am releasing the notes I wrote for the first part of the class into the wild. For this first part, I had set myself a few goals: I wanted to use only the most fundamental notions of geometry,  I wanted a plethora of interesting examples, and I wanted to be able to prove a substantial theorem. Finally, I needed to be able to give homework problems. 

Parallel

The solution was to study incidence geometries, specializing pretty quickly to affine and projective spaces over arbitrary fields. So I did not develop axiomatic projective geometry, but rather taught the computational skills needed to quickly get to the geometry of conics in projective planes. This provided plenty of  exercises. Affine and projective transformations are intensely used in order to prove theorems or to simplify computations. The big theorem I prove at the end is Poncelet’s theorem.

Hyperrat

The second half of the course? This deals with the two-dimensional geometries where we have circles: Möbius, Euclidean, spherical, hyperbolic. Emphasis is again on groups, and here in particular on reflection groups, proving Dyck’s theorem at the end. But I am not quite happy with the notes yet, so this part will have to wait.

Fano3

So here is part I. Enjoy.

Notes on Geometry – Part I: Incidences

 

 

 

 

 

Advertisements

Ends and Handles

Mathematics gets most exciting when new connections between different areas are discovered. In the theory of minimal surfaces, maybe the most fruitful discovery of this sort was Robert Osserman’s theorem from 1964 that a complete minimal surface of finite total curvature has the conformal type of a compact Riemann surface punctured at finitely many points, with the Weierstrass data extending meromorphically to the compact surface. This was a giant step from the much earlier discovery of the Weierstrass representation, that provided a first link between minimal surfaces and complex analysis.

Symfinite

However, at that time, the only known examples where of genus 0, i.e., punctured spheres, and of those only the catenoid (and the plane) were embedded. In fact, it is pretty easy to make examples like the one above: punctured spheres with many ends that will intersect.

This changed dramatically in 1982 when Celso José da Costa constructed a minimal torus with three ends that was proven to be embedded by David Hoffman and Bill Meeks in 1985. Examples with more ends and of higher genus followed rapidly, all nicely embedded. But there was a pattern: It looked like that if you wanted n ends, you needed to have genus at least n-2. This is the Hoffman-Meeks conjecture. For n=2 this follows from a theorem of Rick Schoen. But why can’t we have (say) a torus with four ends?

Fourends

All attempts to produce such an example have failed. In the image above, the ends will intersect, eventually. On the other hand, there is a fair amount of evidence that there are examples of genus g with precisely g+2 ends. Below is such a surface of genus 3 with 5 ends.

Dh11

That such examples should exist for any genus is supported by the Callahan-Hoffman-Meeks surface, a periodic version of the Costa surface. One just needs to chop it into pieces and put catenoidal ends at the top and bottom…

Chm

By recent work of Bill Meeks, Joaquin Perez, and Antonio Ros, the number of ends of a complete, embedded minimal surface of finite total curvature is bounded above by some constant (which is not explicit).

But even the case of tori remains very much open.

Eraserhead (Games on Circles I)

This is not about the film by David Lynch. Eraserhead is played by two players on finite graph with some vertices occupied by erasers. At each turn, the player chooses one eraser, moves it to an unoccupied adjacent edge, thereby erasing the connecting edge. The player who moves last wins.

Let’s analyze this for cycle graphs.
Eraserhead1 01

If played with just one eraser, the first player chooses the direction, and all other moves are forced, until the eraser has erased all edges. So the first player wins if the cycle graph has an odd number of vertices. That was boring.

For two erasers, it gets slightly more interesting, but the outcome is the same: The first player can win if the number of vertices is odd. The two erasers divide the graph into two components whose number of vertices have different parity (3 and 4 in the example below).
Moving an eraser into the even component would be a mistake, as the second player will then move into the same component with the other eraser. This leaves an even number of moves for both players, and the second player will win.

But a winning move for the first player consists of moving one eraser into the odd component. This leaves the second player with two choices: Moving the other eraser either way leaves an odd number of moves for both players, and the first player wins. If the second player moves the first eraser again, the first player can move either way and will win.

Eraserhead2 01

So while a little harder, this was still easy. Does this even/odd pattern for winning and losing persist with more erasers? At first, it seems so. For any number of erasers (except the cases of no erasers and erasers everywhere, which leave no moves to begin with), the first (resp. second) player can always win with if the cycle graph has an odd (resp. even) number of vertices — up to cycle graphs with 8 vertices. For the following position with three erasers, the first player has no winning move. There are three essentially different moves, and the diagram give winning responses for the second player.

Eraserhead3 01

The first line is interesting. With the first player to move again, there are still 8 edges to delete (possibly). If the first player moves with the topmost eraser right, this will actually happen, and the first player will loose. To prevent this, s(he) must move that eraser to the left. This leaves all erasers in one component with a total of four edges left. This looks like a good thing, but no matter how they play, only three edges will be deleted, and the second player must win.

So the game does get complicated. What helps is to know the nimbers for simple subpositions, like chains with or without erasers at the end. For instance, the line graph with n vertices and one eraser at the end has nimber 1 for odd even n and 0 for odd n. Similarly, the line graph with n vertices and erasers at both end has nimber 0 for odd even n and 1 for odd n. This is quite trivial, of course, as all moves are forced. More surprisingly, for the line graph with two erasers at the end and a third eraser in between, the nimbers are again 1 for n odd, and 0 for n even, except when n=3 or n=4. Then the nimbers are 0 and 2, respectively. So things start off with promising simple patterns, but then deviate. Below I have, for line graphs of length 12 and 13, respectively a unit cube at coordinate (x,y,z) if the position with erasers at x, y, and z is a lost position for the first player.

Lost12 13

Finally, below, the corresponding images for cycle graphs, viewed diagonally to emphasize the symmetry. The discrepancy is baffling.

Lostcycle3 12

Stellating the Icosidodecahedron in Black and White

DSC 1737

It is also this time of the year to chase away the dark hours by making presents. As in previous years,
we will make a stellation out of paper without glue. This year, we are going to stellate the Icosidodecahedron, one of the fancier Archimedean solids.

Icosidodecahedron

The stellation is quite simple, it is also a compound of the dodecahedron and icosahedron. The simpler compounds of a Platonic solid with its dual are also doable, see the post from two years ago.

Compound

To make it, we will need 20 triangles and 12 pentagons, so printing and cutting two of the templates below will do. I suggest to print four templates in two different colors and to make two models.

StellaDodecaIcosa

Then we start by sliding five triangles into one pentagon like so:

DSC 1739

Then we add five pentagons between two adjacent triangles.

DSC 1740

Next another five triangles:

DSC 1742

Now we have finished one half of the model. This already would make a nice dome for the backyard.

You can make another half and try to attach them, but I think it is easier to just keep going.
This next step is a little tricky, because to prevent the polygons from falling out, it is best to add a ring of alternating pentagons and triangles. When done, it looks like this:

DSC 1746

The last two steps (add five more triangles and one more pentagon) are then pretty clear, but still tricky because you have to insert the new polygons in four or five slits essentially at once.

DSC 1750

Instant Insanity

This post is about a mathematical puzzle and not the current state of daily affairs. The puzzle consists of four cubes, with faces colored in four colors:

Cubes

If you want to make your own, you can print out the nets below and fold.

Insanenets

The goal is to stack the four cubes together so that each of the four long faces of the 4 x 1 x 1 tower show all four colors.

According to Jerry Slocum, this puzzle goes back to 1900 when Frederick A. Schossow marketed a version of it under the name Katzenjammer Puzzle. Katzenjammer is German for hangover…

It has since appeared in many variations. Its latest incarnation under the current name Instant Insanity was discovered by Frank Armbruster and has been marketed by Parker Brothers since 1967.

We will solve he puzzle using graph theory. Each cube will get encoded in a graph. To do so, we use as vertices the colors (yellow, orange, purple, and green), and connect two colors by an edge if the two colors occur on opposite faces of the cube. Thus we obtain for each colored cube a graph with four vertices (colors) and three edges (opposite faces).

Singlenets

Before we continue, let’s see why these arbitrary looking graphs contains all the information about the cubes that is necessary to play the puzzle: If the graph of a cube is given, we know all colors of pairs of opposite faces for that cube. Using a blank cube, we can first color the front and back face with a pair of these colors. It doesn’t matter which color we pick for the front, because we could turn the cube over. Using a second edge of the graph, we then color the left and right face with the two colors of the end points of the edge. Again it doesn’t matter which color we use for the left side, because there is a rotation fixing front and back that flips left and right. Finally, there are two possibilities remaining for coloring the top and bottom face of the cube. These lead to truly differently colored cubes, but both are equivalent for solving the puzzle, as the top and bottom colors of the tower don’t matter for the puzzle.

Coming back to solving the puzzle, we combine the four graphs we have created for each cube into a single graph with multiple edges. The edges are now labeled from 1 through 4 to indicate from which cube they come. How does this graph help us to solve the puzzle?

InstantInsanity

Suppose we have stacked the cubes together so that both the front and back side of the tower show all four difference colors. The four front and back sides of each cube represent each an edge in our graph, which we give a direction so that they always point to the color of the back edge. Let’s mark these edges say blue. Thus we get four blue edges that begin at four different colors and end at four different colors. As there are just four colors, each vertex has an edge ending and an edge beginning there. This means that following the blue edges, we have found a doubly Hamiltonian circuit – a cycle or collection of cycles that pass through all four vertices (colors) of the graph, and uses edges with each of the four labels (cubes).

Vice versa, any such path can be used to stack the cubes so that front and back side of the tower show all four colors.

Next we will show that any such system of circuits must go once around the square marked by the four colors.

If this were not the case, it would decompose into several components of lengths 1+3, 1+1+2, or 2+2.
While in each case there are Hamiltonian circuits, none of them are doubly Hamiltonian.

Thus we only need to look for Hamiltonian paths that go around the square, and can ignore the loops at orange and green as well as the diagonal connection from purple to orange.

Consider the top and bottom edge, which both have an edge labeled 4. As each edge label can only occur once, one of these two edges must use an edge with a label other than 4. We make a case distinction: First, let’s assume the bottom edge uses label 3. Necessarily then, the right edge then must use label 2, the left edge label 1, and the top edge label 4, and we get the Hamiltonian path marked red.

Now let’s assume that the top edge is using label 1. Thus we have to use for the left either label 2 or 3, and the other label 3 or two for the right edge. Either choice leaves us with label 4 for the bottom edge. One of the choices is the path marked blue, the other one has labels 2 and 3 exchanged in the left and right connections. Thus there are only three different possible Hamiltonian paths.

Solution

To finally solve the puzzle completely, we will need to take care of the left and right faces of our tower. By associating a directed edge for each cube from every left face to every right face, we get a second doubly Hamiltonian path in our graph.
This second path must be edge disjoint with the first, as we cannot use a pair of opposite faces of the same cube twice.

As the second and third of our three Hamiltonian paths are not disjoint, one of the paths we seek must be the red path. This uses edge 2 on the right hand side, so that the second Hamiltonian path can only be the blue one. They are indeed edge disjoint, and thus solve the puzzle.

Reflections on the Letters r,s,t (Groups II)

Continuing the discussion from last week, let’s consider the 3-letter alphabet {r,s,t}. We are allowed to form all possible words in these letters (and their inverses, if you want to), but we agree that rr=ss=tt=1 and (rs)^2=(st)^3=(tr)^6=1. This defines the Coxeter group G(2,3,6). Last time we saw that the very similar group G(2,3,3) is finite, today we will see that G(2,3,6) is infinite. Below is the beginning of its Cayley graph.

Cayley236 01

We travel from one word to the next by appending r,s, or t. This looks much more complicated than what we saw for G(2,3,3), but things become clearer when we look at another group. Consider a yellow triangle with 30, 60, 90 degree angles (writing this as π/2, π/3,π/6 makes 2-3-6 reappear), and let ρ, σ, τ be the reflections at the lines extending its edges.

Reflectiongroup 01

These three reflections generate a group Γ(2,3,6) of Euclidean symmetries which has the yellow triangle as its fundamental domain. The clue is that Γ(2,3,6) = G(2,3,6). We can easily map G(2,3,6) to Γ(2,3,6) by sending R to ρ, s to &sigma, t to τ. This works because ρ, σ, τ satisfy the same relations as r, s, t. It doesn’t work as easily the other way because ρ, σ, &tau could also satisfy other, hidden relations.

Reflpath 01

Let’s look at the word tsrtst. Reading it from left to right gives us a path on the Cayley graph from the initial triangle to a target triangle. Translating from Latin tsrtst to Greek τσρτστ gives a composition of reflections that takes the initial triangle to the same target triangle. This is not completely trivial, you prove it by induction. Remember that the composition is applied from the right to the left, so we also change reading direction.

This observation can be used to show that the translation map G(2,3,6) to Γ(2,3,6) is injective. If a word in G is the identity in $γ, its path in the Cayley graph must be a closed loop. As the Euclidean plane where the tiling lives is simply connected, we can homotope it to a constant path, using elementary operations: Backtracking an edge, or shrinking a loop around a vertex to a point. The former is the accomplished using the relations rr=ss=tt=1, the latter using the other relations. This shows that the geometric homotopy can be realized using the relations of the group, and thus we can reduce the word to the trivial word 1.

Cayley
This is essentially the proof of a famous theorem by Walther Franz Anton von Dyck: The group G(a,b,c) is finite if and only if 1/a+1/b+1/c>1. We have seen the relevant examples in the case
1/a+1/b+1/c>1 and 1/a+1/b+1/c=1. If 1/a+1/b+1/c <1, we need hyoperbolic geometry. Above is a picture of the Cayley graph of G(2,3,7) within the tiling of the hyperbolic plane by (π/2,π/3,π/7)-triangles.

Do and Undo (Groups I)

Groups are mathematical games being played with letters. In the simplest version, we use just one letter (say a), and are allowed to add it to or to remove it from a word. This is the free group of one generator, or the infinite cyclic group.

Cyclic 1 01

Clearly, this game of create and destroy needs more rules. A simple rule is to make it truly cyclic and finite by insisting that after using the letter a say 7 times, we are back where we started. This means aaaaaaa=1, which is a relief, but still not very interesting.

Cyclic 2 01

With two letters a and b, our game expands.

Free2

This Cayley graph is the dual graph of the tiling of the hyperbolic plane by ideal squares, and not accidentally so.

Again we can restrict the rules of the game. Let’s play with the three letters r, s, and t, and insist that rr=ss=tt=1 to avoid any repetitions, and also that rsrs=ststst=trtrtr=1. The result is the Coxeter group G(2,3,3), and after a while playing around with the words, you find its Cayley graph below, neatly laid out.

Dyck233

This is dual to a tiling of the sphere by spherical triangles with angles π/2,π/3,π/3, and this is also not accidentally so.
We’ll see more about this next week.

Cox233