Borromean Rings

ImageThe 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.

Braids

The Borromean rings can also be viewed as a familiar braid on three strands with the ends joined.

Algebraic Topology

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 xyxy‘ is not trivial in the free group (in which the only allowable cancelations are xx‘ = xx = 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.

Threshold security

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.

Boolean logic

The word xy is associated with AND and the word xyxy‘ 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 xyxy‘, 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.

NP-completeness

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.

Group testing

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?

Students’ attention

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.

Beer

Balantine Ale has a logo including the Borromean rings. Cracking open a cold one has a way of grabbing students’ attention in certain circumstances.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s