The Borromean Rings is an arrangement of three interlinked loops. The trio cannot be separated, but, if any one loop is removed, the other two can be separated. This makes for an great classroom activity, for many audiences, and to demonstrate many different phenomena, including algebra, topology, cryptography, boolean logic, and NP-completeness.
Topologist’s twister: an ice-breaker
Ask the audience to form groups of three. Give the definition of the rings, and ask each triple of players to assume the position, where each player makes a loop out of their arms.
The Borromean rings can also be viewed as a familiar braid on three strands with the ends joined.
It’s easy enough to see that any two loops separate if the third is removed, and the that the arrangement has three-fold symmetry. But how to prove that the original arrangement cannot be separated? This is a standard result in introductory algebraic topology that is tough to do fully from first principles, but we can still demonstrate using algebra to get a handle on the topology. First, what does “separated” mean? Two rings are separated if there’s a ball with one ring in the interior of the ball and the other ring disjoint from the ball. Next, assuming that a circle can not be deformed to a point, we consider the rings. Retract the complement of the red and blue rings into a figure 8. The green ring lies in the figure-8 according to the word xyx’y’ (where the prime indicates inverse). Since the word xyx‘y‘ is not trivial in the free group (in which the only allowable cancelations are xx‘ = x‘x = 1), the rings do not separate.
Intuitively, the only thing that matters is the number of times the green encircles each lobe of the figure 8, and in which order. With pipe cleaners, we can distort the rings until we can see that the green winds around the blue, then winds around the red, then unwinds around the green, and unwinds around the red.
H/T to Shachar Lovett. How can you lock a bicycle to rack with three flexible cable locks, so that opening any two locks frees the bike, but opening any one lock leaves the bike secure? Topologists don’t ride bikes like you and me. Think of three rigid loops for locks, while the bike and rack together form a single flexible loop. Wind the bike/rack combination through the rigid loops with word xyzx’y’z’. It is easy to see that this word is not trivial, if any one of x, y, z is mapped to 1 the word remains non-trivial, but if two of the generators are mapped to 1, the word vanishes.
The word xy is associated with AND and the word xyx‘y‘ is associated with OR. If we wind the bike/rack combination through two locks according to word xy, we need to open lock x AND lock y to free the bike. If we wind the bike/rack combination according to word xyx‘y‘, then we need to open lock x OR lock y to free the bike. (In this case, the two locks and the bike/rack combination form the Borromean rings.) So we have implemented AND and OR. Since AND and OR are complete for the monotonic boolean functions (opening more locks only helps to free the bike), we can now see how to implement any access structure to the bike. And note that we have seen again how algebra (symbols, anyway) help to get a handle on the messy topology.
The following problem is easily seen to be NP-complete. Given an arrangement of 2n cable locks ensnaring a bike and rack, can we free the bike opening at most n locks? We give a reduction from a 3-satisfiability instance on n variables. For each variable x, provide a lock marked x and a lock marked NOT-x. A 3SAT instance is monotonic over literals (x and NOT-x), so implement it. Also implement x OR NOT x, and repeat for each variable. That way, to free the bike we must open at least one of the literals x and NOT x, and, if we free the bike opening exactly n, we must open exactly one of x and NOT x.
We can regard the bike/rack combination (called a tester in this paragraph) as testing for defects among the locks: If the bike goes free, there is a defect. As noted above, any monotonic function can be tested this way; traditional group testing tests the OR of a subset. We can have multiple testers. From all the outcomes of tests, can we identify the defective locks?
Colors and textures
Give the audience members three different-colored pipe cleaners with which to construct the rings (or 5 pipe cleaners to solve the bike lock problem, below). Pipe cleaners have bright colors and fuzzy textures and moldable metal, all of which is more memorable than anything possible with pencil and paper.
Balantine Ale has a logo including the Borromean rings. Cracking open a cold one has a way of grabbing students’ attention in certain circumstances.