Theorem Thursday: Tutte’s Theorem, Magic, And Happy Endings

To wrap up my two-month Theorem Thursday project I have another request to fill. And it’s another from Gaurish, whose requests for the Leap Day A To Z inspired so many interesting posts.

Tutte’s Theorem

I admit I had not heard of Tutte’s Theorem before Gaurish’s request and I had to spend time working up to knowing what it was and why it was useful. I also admit I’m not completely sure I have it. But I’m happy to try to accept with grace corrections from the people in graph theory who know better.

It comes back to graphs. These are a bunch of points, “vertices”, which have curves, “edges” connecting pairs of them. This describes a lot of systems. Bunches of things that have to connect are naturally graphs. Connecting utilities to houses gave the first example I called up last week. The Internet’s made people vaguely familiar with the idea of bunches of computers linked to bunches of other computers. Social networks can be seen as graphs; each person is a vertex, her friendships edges connecting to other vertices.

In a graph not every vertex has to be connected to every other vertex. Not everyone needs to be friends with everyone else, which is a relief. I don’t want to point fingers but some of your friends are insufferable. I don’t know how you put up with them. You, you’re great. But the friends of a friend … yeeeeeeesh.

So we — mathematicians, anyway — get to wondering. Give me a graph. It’s got some vertices and some edges. Let’s look at only some of these edges. Each edge links to two vertices. Is there a subset of the edges that touch every one of the vertices exactly once? Sometimes there are; sometimes there aren’t. If there are, we have a “perfect matching”.

We look at this sort of thing because mathematicians learn to look at coverings. Coverings are what they sound like. What’s the smallest set of some standard item you need to … cover … all the stuff you’re interested in this problem? I think we’re bred to look for coverings in Real Analysis, because the idea of covering space with discs gives us measure. This gives us a rigorous idea of what length is, and what dimensions are, and lets us see there have to be more irrational than rational numbers and other interesting results like that. Mathematicians get used to looking for this sort of thing in other fields.

Tutte’s Theorem is about perfect matchings. It says what conditions a graph has to have to have a perfect matching. It’s based on striking subsets of the vertices from the original graph. The accompanying edges go too. What’s left might be connected, which means just what you think. You can get from any vertex in the decimated graph to any other vertex by following its edges. Or it might be disconnected, which means again just what you think. Mathematics is not always about complicated lingo.

Take the survivors. Count how many of the remaining connected components have an odd number of vertices. Is that less than or equal to the number of vertices you struck out? If it is, and if it is no matter how many vertices you struck out, and no matter how you arranged those vertices, then there’s a perfect matching.

This isn’t one for testing. I mean, consider what’s easier to do: start from your original graph and test out coloring in some edges to see if you can touch every edge the one time? Take every possible sub-graph of the original graph and count the number of connected sub-pieces with an odd number of vertices? … Well, maybe that isn’t so bad, if you set a computer to do the boring work. It’s going to take forever for your graph with 102 vertices, though, unless it’s a boring network. You have to test every possible removal all the way up to striking 102 vertices. (OK, it’s easy to show it’s true if 102 of 102 vertices are removed from the graph. Also if 101 of 102 vertices are removed. And 100 of 102 is also not hard. But that’s only a couple easy cases left.)

I don’t know the real work the theorem does. It has some neat and implications good for pop mathematics. Take a standard deck of 52 well-shuffled cards. Deal them out into thirteen piles of four cards each. Is it possible to select exactly one card from each pile so that, when done, there’s exactly one of each face value — Ace, Two, Three, Four, up through Queen and King — in the selected set? Indeed it is. I leave it to the Magic In A Minute cartoonists to turn this into a way to annoy a compliant monkey.

Another appealing use for it is in marriage problems. Well, marriage looked to mathematicians like a good source of bipartite graph problems. Society’s since noticed that nobody really hit on a compelling reason for “why does a woman have to marry a man, exactly”. I imagine the change to filter into mathematics textbooks sometime in the next seventy years. But please accept that this problem was formed and solved in the 1930s.

Suppose you have a group of women and a group of men, of equal size. Each woman would be happy married to some of the men in that group. Each man would be happy married to some of the women in that group. Is it possible to match women and men up in a way that everybody is married to at least someone they’d be happy with? We’re not guaranteeing that anyone gets their best possible pairing. We promise just that everyone marries someone they’ll be glad to.

It depends. Maybe this is best done by testing. Work through every possible subset of women. That is, look at every group of one woman, every group of two women, every group of three women, and so on. By group I mean what normal people mean by group, not what mathematicians mean. So look at your group of women. Count how many of the men at least one woman would be content marrying. Is that number equal to or larger than the number of women? Is that number equal to or larger than the number of women, however many women you picked and whichever women you did pick? If it did, great: everybody can marry someone they’re happy with.

Parlor tricks, I admit, but pleasant ones. What are its real uses? At this point I am really synthesizing my readings on the subject rather than speaking from things I’m confident about. If I understand right, though, Tutte’s Theorem is a foundation for the study of graph toughness. That is what you’d guess from the name. It’s about how easy it is to break up a graph into disconnected pieces. It’s easy to imagine real networks with strength or weakness. Image the person that holds a complicated group of friends together, for example, and whose removal devastates it. Consider the electrical network with a few vulnerable points that allow small problems to become nationwide blackouts. I believe it’s relevant to the study of proteins. Those long strands of blocks of molecules that then fold back on themselves. (I haven’t seen a source that says this, but it can’t imagine why it shouldn’t. I am open to correction from sneering protein researchers.) I would be surprised if the theorem has nothing to say about when a strand of Christmas tree lights will get too tangled to fix.

Let me close with a puzzle, a delightful little one. It regards one of the graphs we met last week. K₅ is a complete graph with five vertices. Each vertex is connected to all four of its siblings. It can’t have a perfect matching. Only a graph with an even number of vertices can. Each edge connects to two vertices, after all. So — what is the subset that breaks Tutte’s theorem? It must be possible to strike some set of vertices from K₅ so that the number of stricken vertices is smaller than the number of remaining connected components with an odd number of vertices. What’s that set?

Go ahead and ponder it a while. If you give up I don’t blame you. The answer is at the other end of this link. If you’d like a hint, let me offer this, which you might be able to mouse over to reveal.

It is obvious once you’ve heard what the subset of vertices is, and it is not K₅. The rest of this paragraph is padding so that the size of the spoiler doesn’t give matters away. And by the way I’d like to thank the world at large for doing such a great job not spoiling Star Wars: The Force Awakens. So why could you not give some similar consideration for Star Trek Beyond? I stopped reading TrekBBS for a month partly to avoid spoilers and then I started getting them everywhere I looked. Not cool, world.

Good luck!

A Summer 2015 Mathematics A To Z: measure

Measure.

Before painting a room you should spackle the walls. This fills up small holes and cracks. My father is notorious for using enough spackle to appreciably diminish the room’s volume. (So says my mother. My father disagrees.) I put spackle on as if I were paying for it myself, using so little my father has sometimes asked when I’m going to put any on. I’ll get to mathematics in the next paragraph.

One of the natural things to wonder about a set — a collection of things — is how big it is. The “measure” of a set is how we describe how big a set is. If we’re looking at a set that’s a line segment within a longer line, the measure pretty much matches our idea of length. If we’re looking at a shape on the plane, the measure matches our idea of area. A solid in space we expect has a measure that’s like the volume.

We might say the cracks and holes in a wall are as big as the amount of spackle it takes to fill them. Specifically, we mean it’s the least bit of spackle needed to fill them. And similarly we describe the measure of a set in terms of how much it takes to cover it. We even call this “covering”.

We use the tool of “cover sets”. These are sets with a measure — a length, a volume, a hypervolume, whatever — that we know. If we look at regular old normal space, these cover sets are typically circles or spheres or similar nice, round sets. They’re familiar. They’re easy to work with. We don’t have to worry about how to orient them, the way we might if we had square or triangular covering sets. These covering sets can be as small or as large as you need. And we suppose that we have some standard reference. This is a covering set with measure 1, this with measure 1/2, this with measure 24, this with measure 1/72.04, and so on. (If you want to know what units these measures are in, they’re “units of measure”. What we’re interested in is unchanged whether we measure in “inches” or “square kilometers” or “cubic parsecs” or something else. It’s just longer to say.)

You can imagine this as a game. I give you a set; you try to cover it. You can cover it with circles (or spheres, or whatever fits the space we’re in) that are big, or small, or whatever size you like. You can use as many as you like. You can cover more than just the things in the set I gave you. The only absolute rule is you must not miss anything, even one point, in the set I give you. Find the smallest total area of the covering circles you use. That smallest total area that covers the whole set is the measure of that set.

Generally, measure matches pretty well the intuitive feel we might have for length or area or volume. And the idea extends to things that don’t really have areas. For example, we can study the probability of events by thinking of the space of all possible outcomes of an experiment, like all the ways twenty coins might come up. We find the measure of the set of outcomes we’re interested in, like all the sets that have ten tails. The probability of the outcome we’re interested in is the measure of the set we’re interested in divided by the measure of the set of all possible outcomes. (There’s more work to do to make this quite true. In an advanced probability course we do this work. Please trust me that we could do it if we had to. Also you see why we stride briskly past the discussion of units. What unit would make sense for measuring “the space of all possible outcomes of an experiment” anyway?)

But there are surprises. For example, there’s the Cantor set. The easiest way to make the Cantor set is to start with a line of length 1 — of measure 1 — and take out the middle third. This produces two line segments of length, measure, 1/3 each. Take out the middle third of each of those segments. This leaves four segments each of length 1/9. Take out the middle third of each of those four segments, producing eight segments, and so on. If you do this infinitely many times you’ll create a set that has no measure; it fills no volume, it has no length. And yet you can prove there are just as many points in this set as there are in a real normal space. Somehow merely having a lot of points doesn’t mean they fill space.

Measure is useful not just because it can give us paradoxes like that. We often want to say how big sets, or subsets, of whatever we’re interested in are. And using measure lets us adapt things like calculus to become more powerful. We’re able to say what the integral is for functions that are much more discontinuous, more chopped up, than ones that high school or freshman calculus can treat, for example. The idea of measure takes length and area and such and makes it more abstract, giving it great power and applicability.