# Posts Tagged ‘graph theory’

June 23rd, 2014

Here’s an article from the BBC about the so-called “Birthday Paradox” applied to the teams of the 2014 FIFA World Cup. The Birthday Paradox is the term for a common failure of intuition. It’s rather unlikely for two people to share a birthday, and people usually expect it to remain unlikely for any two people in a group of moderate size to share a birthday. In fact, the number of pairs of people grows quadratically, so the probability that there is at least one pair sharing a birthday hits 50% more quickly than people often assume.

It turns out that the tipping point for the size of the group is 23, which is exactly the size of a World Cup soccer team roster. And the teams this year illustrate the balance perfectly: exactly half of them have players that share a birthday. As Ξ points out on the math blog 360, even though 50% is the proportion of teams we would expect to have birthday-sharing-players, it’s actually pretty unexpected to hit the expected value exactly. That might be a “Birthday Paradox” Paradox.

But not the one that I set out to write about! Situations like the Birthday Paradox can come up in all sorts of contexts. Four years ago I noticed an interesting fact: all of the groups in the first round of the 2010 World Cup had different score results. This seemed unlikely to me, but was it really? I’d need to do some more investigation to find out. 2010 was indeed the first time that all of the scores had been different since the World Cup expanded to eight groups in 1998, but there had only been a total of four World Cups to that point, not enough for a good statistical sample.

A bit of background: In the group stage of the World Cup, there are eight groups of four teams; in each group all of the teams play each other in a round-robin mini-tournament. Each team receives three points per victory and one point per draw. The top two teams in each group advance into the next stage, a four round single elimination tournament. (There are tiebreaker rules for determining who advances when the second and third teams tie; I won’t get into those here.)

You can model group results with with oriented graphs: directed edges correspond here to a victory for the team that the edge points away from, and absent edges stand for ties. There are 42 distinct oriented graphs with four vertices, but only 40 different group scores; in two cases the same score can be achieved with two different graphs. For the sake of mathematical simplicity, let us assume that every game that is played has an equal probability of being a tie, a win for team A, or a win for team B. This makes the problem easier to model at the expense of some realism. In the real World Cup, there are better teams and worse teams, and the teams are seeded into groups such that there is approximately one team belonging to each quartile in each group. (Concerns like geographical distribution may interfere with this ideal.) This means that results with cycles of victories are probably a little less likely in the real world than in our model, as they would require a team that is worse on paper to defeat one that is better. Upsets do happen, but their unlikelihood is what makes them upsets. Additionally, the actual proportion of ties may diverge from 1/3, although this is not in fact a terrible estimate. In 2010, 14 of the 48 group matches were draws.

Complicating matters, the graphs are not equally likely to appear. Notice that a graph with no symmetry (such as the 9-6-3-0 graph in the upper left corner) can occur in in as many ways as there are permutations of the four teams. (There are 24.) At the other extreme, the most symmetrical graph belongs to the group with all ties in the lower right, which can occur in exactly one way. In general, the graphs with more symmetry can be made in a smaller number of different ways. Counting the scores that can be achieved with two graphs, there are 2 scores that can be reached 36 ways, 21 that can be reached 24 ways, 9 that can be reached 12 ways, 3 that can be reached 8 ways, 2 that can be reached 6 ways, 2 that can be reached 4 ways, and 1 that can be reached 1 way. We can check that we’ve got them all by noting that this adds up to 729, or 36, which is the number of different ways six games can go.

I wrote a Python program that found the above counts and then used them to determine the probability that no two groups would have the same score in our model. But before I did that, I wrote another program to simulate the results of a group stage by randomly picking the results of each game. Even though this simulation couldn’t give an exact answer to the problem, I’m glad I wrote it. It was a much simpler program than the one I wrote to get the exact answer, so it was easier to convince myself that it was performing correctly. In the process of writing the final program, I made a number of mathematical and programming errors that led to incorrect results; if I did not have a good idea of the approximate value of the answer, I might have stopped without knowing there was an error.

The end result? The probability of all eight groups having different scores in my model is 393101879398962298880/984770902183611232881, or about .39918. So I was right that all groups having different scores was the less likely case, but wrong to think that it was particularly unlikely. I think a big part of why I was wrong was that I knew about the Birthday Paradox. It primed me to think that no two items in a group sharing a property would be unlikely, in a more general sense than is actually the case. This is the “Birthday Paradox” Paradox that I fell into.

Some puzzles:

Which is more likely to have all different group scores? The men’s World Cup, or the women’s World Cup? The women’s World Cup has had four groups since 1999. (This is a trickier question than it seems, and may illustrate the limitations of the random result model.)

What proportion of ties would maximize the probability that all group scores are different?

We might explore the probability of all group scores being different in various past and hypothetical tournament setups. What if there were more or fewer groups? What if wins counted for two points, as was once the case? What if there were five teams per group? In the cases with four teams per group where there are two different graphs that give the same score, the sets of team records are the same. (For example, in the 7-4-4-1 groups, the records are set of team records for both (expressed as wins-losses-ties) are 2-0-1, 1-1-1, 1-1-1, and 0-2-1.) With 5 or 6 teams, is it possible to come up with a group score that can be formed by two different sets of team records?

(Thanks to Joe DeVincentis, who took up the main puzzle when I posed it on gplus. Also, I should note that the correspondence between World Cup group results and oriented graphs is not original to me; here’s another exploration of the connection.)

## Crossed Sticks: Compatability Variations

August 19th, 2013

So far, the crossed stick puzzles I’ve designed have been limited by the two-dimensional nature of designing for lasercut materials. But 3D printing presents another option for puzzles that can’t be formed from flat pieces.

One new area to explore is connector compatibility variations. In most of the puzzles we’ve looked at thus far, there are two types of connectors or slots, ups and downs, or deeps and shallows, and each type matches the opposite. Suppose instead we wanted two types of connectors where each matches itself rather than the other type. It can’t be done (as far as I can tell) with lasercut slots, but it can be done! My first 3D printed puzzle prototypes are shown below: Consider connectors made of pairs of studs and holes as in the the puzzle on the left side of the image above. When we flip and rotate a piece with this type of connector in order to join it at right angles with another such piece, the studs on each piece match the holes on the other. But this only works when the two connectors have the same orientation. When a connector with a vertical stud pair is matched with a connector with a horizontal stud pair, both pairs of studs end up at the same position, so the connectors can’t join. We can call this connection scheme the same-match scheme, as opposed to the other-match scheme.

With diagonal pairs of studs and holes, (as on the right side above) flipping the piece swaps the positions of the studs and holes instead of keeping them in place. This means that the resulting puzzle will use the standard compatibility matrix. Initially, this may seem disappointing: after all, this is just the puzzle we could get without using stud and hole blocks. But in fact this setup allows us to use both compatibility schemes! If we place both layers of pieces so that the studs face the same direction, we have a puzzle using the same-match scheme.

It should be pretty clear that these two schemes are the only viable connection schemes for two connection types. When we move to three connection types, things get a little more complicated. It will help to represent a connection scheme as a graph, where the vertices represent connection types, and compatible types are connected by an edge. Since self-compatibility is possible, the graphs may contain loops from one vertex to itself. Here are the graphs for the two binary connection schemes: One example of a ternary connection scheme can realized with lasercut slots. Let the three slot types be deep, middle, and shallow, where middle depth slots match themselves, and deep and shallow match each other. Here’s the graph for that scheme: The advantage of working from graph representations of connection schemes is that we can come up with the graphs first, and then worry about how we will physically realize a puzzle using that scheme later. So let’s just doodle some promising three-vertex graphs: Some constraints become apparent at this point. First, there can’t be a vertex with no edges, because that would represent a connection type that can’t connect to anything, and its presence would immediately render a puzzle unsolvable. Vertices that connect to everything (including themselves) are also problematic. Such a connection type doesn’t add to the challenge of a puzzle, and if all vertices had this property, the puzzle wouldn’t be a puzzle at all. I’m inclined to remove graphs with this kind of vertex from consideration for the time being, allowing that I may be wrong, and interesting puzzles using this kind of vertex may indeed be possible.

Another problem that can occur is that vertices may be indistinguishable. For example, consider this graph: Both the rightmost and the leftmost vertex in this graph are connected only to the center point. What this means in practice is that it doesn’t matter whether a connector has the leftmost vertex type or the rightmost vertex type; the connectors will behave exactly the same. But if this is so, there is effectively no difference between this connection scheme and the other-match binary scheme. For the connector types in a scheme to be distinguishable, each must have a different neighbor set.

A quality of a connection scheme that may be desirable is balance. Consider the following graph: The rightmost vertex only connects to one vertex, while the others both connect to two. Now imagine a puzzle that uses equal numbers of all three connector types, as we have typically done so far. Since we need all rightmost type connectors to match something, we have to use up all of the middle type connectors for this purpose. This means that the leftmost type connectors must all match themselves. Since no leftmost type connectors can match middle connectors, we find ourselves effectively using the three-height slot scheme. This doesn’t mean that this scheme is entirely unviable, but our piece sets are going to have to look a little weird to make it work. For the moment we will mainly concern ourselves with balanced schemes, where each vertex has the same degree. (That is, they are connected to the same numbers of vertices.)

Another consideration that will be important is the density of the graphs. This quantity is the ratio of the degree of the vertices (or the average if the scheme is unbalanced) to the total number of vertices. The density will have an effect on the difficulty of the puzzle and the number of solutions, since a high density means that if we randomly distribute connections, each connection has a high likelihood of being valid.

The following are the “good” ternary connection schemes under the above constraints. The schemes in the top row have density ⅓, and those in the bottom row have density ⅔.

I could keep going about how we could realize some of these schemes in 3D printed puzzles, and I could get into quaternary schemes, but longpost is already long, so I’ll save this for later.

## Chromatic Number of the Plane Is Still Less Than Or Equal To Seven

May 6th, 2013

Well, it was worth a shot. The Chromatic Number of the Plane is defined as the number of colors required to paint the plane such that no two points one unit distance apart are the same color. There are very simple figures that demonstrate a lower bound of 4 and an upper bound of 7 for this number. But this is more or less where knowledge of this problem has stood for the last 50 years. (See the Wikipedia page on this problem for more info.)

I didn’t really expect that I could make a breakthrough, given that real mathematicians have given serious thought to this problem and gotten nowhere, but I thought this would be fun to play with. One potentially useful starting point is to consider how much of the plane one single color could cover. A disk of unit diameter is the biggest blob we can make without two points a unit distance apart. (We’ll allow some fudging about the points on the perimeter of the disk.) We can then pack these disks into a triangular array such that the distance between nearby disks in the array is also one unit. (It’s not clear to me whether we couldn’t get a slightly higher proportion of the plane in one color by flattening the parts of the circles that are closest to other circles. But in any case, the packing with circles should be close to the best we can do.)

It was easy enough to make an array of disks in this fashion using Inkscape. I then copied the array five times, gave each of the six copies its own color, and made them all translucent, so that the overlapping areas could be readily distinguished. The point of this exercise is this: if I could find a way to arrange the six arrays of circles so that they completely covered a region of the plane, I would be able to demonstrate the existence of a coloring that uses only six colors. In other words, I would have decreased the upper bound of the chromatic number of the plane by one, which would have been a significant mathematical result. Note that the circles could and would overlap; any areas of overlap would consist of points that could belong to either color in a valid coloring.

As you can see, I failed. The illustration above was about the best I could do. The white gaps represent areas that could not be colored with any of the six colors. Failing here really proves nothing. Even if I could prove that no coloring using disk arrays like these could work, it wouldn’t prove that there wasn’t some other way to partition the plane that would work better. In fact, Ed Pegg found a configuration where the amount of space needed by the seventh color is very tiny indeed, which gives some hope that 6 colors is possible.

If I could prove that this array of circles really represented the greatest possible proportion of the plane that could be taken up by a single color, (which I can’t) I would in fact be able to improve the lower bound of the CNP. If I didn’t make a mistake, the proportion of the plane taken up by the array of circles works out to π/(8·sqrt(3)), or about .227. Since this is less than ¼, that would mean that the total area that could be taken by 4 colors could not cover the whole plane. Part of the problem here is that even if one could show that the array of circles had the highest proportion of the plane of any “nice” arrangement, it might turn out that an actual coloring of the plane with the fewest colors would end up taking the form of interpenetrating fractal foams, where no individual piece has a measurable area.

## Pentaedges

April 10th, 2011

In graph theory, a graph is a set of vertices along with a set of edges that each connect exactly two different vertices. As a polyformist, it seems natural for me to ask, can we make interesting sets of polyforms out of them? We usually require polyforms to be connected, and we usually look at sets of all polyforms of size n, for some positive integer n. One obvious possibility would be to use sets of all connected graphs of n vertices. But these quickly grow to unwieldy numbers; additionally, they suffer from the problem that once n hits 5, some graphs are non-planar, or impossible to represent in a plane without crossings. This would restrict any search for elegant figures to use in tiling problems with them.

Alternatively, we could look at sets of connected graphs with n edges, which I will call polyedges. There are no non-planar n-edges until size 9. There are 12 pentaedges, the same as the number of pentominoes, and I hope to show that this is a versitile and interesting set of polyforms. The 12 pentaedges

(The term polyedges is used in some sources to refer to what are more commonly referred to as polysticks, i. e. connected sets of segments in a (typically square) lattice. However, I have need of a term, and polyedge seems so clearly the right one that I feel justified in repurposing it.)

In making tiling problems for polyedges, we treat them like polysticks, allowing polyedges to meet at a vertex but not allowing edges to overlap between forms. Now, one important problem remains: what graphs should we use as patterns for them to tile? We are unconstrained by geometrical considerations, which in the case of polyominoes, for example, pull us toward making rectangles. But we can still use symmetry. Not only are highly symmetrical graphs particularly elegant, but symmetry can narrow the space of solutions; since polyedges are very flexible, this is probably desirable. It will help that the total number of edges in the set is 60, a number with many factors, which should help in our search for symmetrical patterns.

Here are the pentaedges tiling 4 copies of K6, the complete graph (all vertices are connected) with 6 vertices: This pattern has a truly dizzying amount of symmetry. Every permutation of the vertices in a complete graph maps the graph to itself. There are 6! = 720 such mappings (or automorphisms) for each K6. Since we can permute all four copies independently, on top of which we can arbitrarily reorder the copies themselves, the full pattern has 7204 · 4! = 6,449,725,440,000 automorphisms.

On the other hand, it’s non-planar, and we might want to tile some planar patterns. One highly symmetrical planar pattern with 60 edges is a pair of icosahedra. I show them squished onto a plane for clarity below, but as graphs they’re still equivalent to the 20-sided dice that role-playing gamers use. Notice that I used 6 colors to distinguish the pentaedges in the figure above. In fact, I had to, since each of the pentaedges touches each of the others within each icosahedron. We could instead try to minimize the number of colors required.

Problem #22: Tile a pair of icosahedra with the pentaedges using only 3 colors, with no two pentaedges of the same color meeting at a point. (It may help to know that there must be 11 vertices where the degrees of the vertex for each adjoining pentaedge are 2, 2, and 1, 7 where they are 3, 1, and 1, and 3 where they are 3 and 2. This can be obtained by counting the total number of vertices of each type in the 12 pentaedges and setting up a system of equations; I won’t get into the details here, but I’ll put them in a comment.)

The pattern above has 28,800 automorphisms. It’s not the most symmetrical planar pattern possible. A set of 4 pentagonal dipyramids has 3,840,000 automorphisms. After finding the other tilings in this post, I got lazy wanted to let others join in the fun, so I’m leaving the problem to you:

Problem #23: Tile a set of 4 pentagonal dipyramids with the 12 pentaedges.

With polysticks, we often like to forbid solutions from containing points where two polysticks cross. We can do the same with polyedges, if we set up the pattern properly: Notice the trick I played with the pentagonal (or 5-cycle) pentaedge at the bottom of the figure, putting the 5-star pentaedge inside it. In the previous problem, we couldn’t tile the icosahedra without any crossings, because one pentaedge contains a 4-cycle, which can only be placed on an icosahedron with an edge connecting two opposite corners, and the pentaedge containing this edge must cross the 4-cycle. Can we find a pattern where the pentaedges containing 4- and 5-cycles can both enclose one or more other pentaedges, so that the pattern contains only triangular faces and can still be tiled without crossings? Here’s a candidate that can be inscribed on a cube; in this case it seems clearer to show the cube in an unfolded state than to squish it as we did with the icosahedra. Problem #24: Tile the above figure with the pentaedges. (Keep in mind that in the unfolded version, the edges that fold together count as a single edge. The pentaedges that are already placed are just for illustration, and can be placed differently in a solution.)

To make it a bit easier to communicate solutions or new problems you find, I’m providing source svgs (made in Inkscape) for some of the images above. They contain copies of the relevant patterns in plain black, which can be turned into a solution by recoloring the edges.

Problem #22 (Icosahedra)
Hexagonal figure
Problem #24 (Cube with triangles)

This post expands on material at my non-blog. Theoretically, I’m using this blog to write more exploratory material in the service of the non-blog, where I intend to collect it in a more digested form. However, lately I’ve been more poaching the non-blog for material to use here, and I haven’t gotten around to updating the non-blog as I mean to. Nevertheless, if you like what you’ve been seeing here, you should check it out, as it contains most of my polyform discoveries from the ’00s.

## Polysticks on a Regular Spanning Subgraph

December 24th, 2010

If any of you haven’t seen them yet, Vi Hart’s “Doodling in Math Class” videos are some of the best expressions I’ve seen of the joy of Recreational Mathematics. The Snakes and Graphs one is especially good, and it contains, despite all of the Internet Meme Years that have passed, a Snakes on a Plane reference.

Ed Pegg wrote a Math Games column in 2006 riffing on the notion of Snakes on a Plane. There’s some great stuff in there, but one could probably fill another column with material that didn’t make the cut. For example, he includes strip polyominoes, which have squares on each end that border only one other square, and are connected by a path of squares that border exactly two others. But linear polysticks, despite being at least as snakey, are absent. What can we do with linear polysticks? To me, they seem to cry out to be tiled onto some closed curve on the square grid. One could imagine some variant of Slitherlink (A Japanese puzzle type described in Ed Pegg’s column) where one would use linear polysticks to form the solution. (For another example of polysticks being used to tile figures on a square grid, see my previous post, Polystick Problems from Polyomino Solutions.)

I was, however, drawn to another source of closed curves. You can move a rook on a rectangular board in a series of single steps that visits every square once and returns to its starting point. Such a sequence is called a closed rook tour, and is the subject of an excellent article by George Jeliss. In graph theory terminology, a closed rook tour is a Hamiltonian of the graph with vertices that correspond to the squares on the board, and edges that connect vertices of neighboring squares. Closed rook tours have been enumerated for small rectangular boards, and it looked like there were enough of them to make it reasonable to hope that one of them could be tiled by a set of polysticks.

The nine linear tetrasticks seemed like a good place to start, and have a convenient total length of 36, which is just right for a 6×6 square. Sadly, the linear tetrasticks have a parity problem that prevents them from forming a closed curve. (A closed curve must have even numbers of both horizontal and vertical segments. Three of the tetrasticks have odd horizontal / vertical parity, and so the full set must have odd numbers of each.) But we can repair this parity problem by adding the 4 linear tristicks to the mix, giving us a total length of 48, which should work on a 6×8 rectangle. Adding the tristicks also improves the flexibility of the set and should make solutions easier to find, which was welcome as I was trying to solve the puzzle manually. #17: Put these ——ing snakes on a ——ing closed rook tour of a 6×8 rectangular grid.

As you can see, I didn’t quite find a solution myself, but I got close! Perhaps you will be luckier, more persistent, or smarter than I.

Update, 2011-2-4: George Sicherman has found a solution! Where to go next? Well, a reasonable extension would be to look at grids where every vertex has three edges instead of two. Unfortunately, any finite section of a square grid has to have corners which can only have two edges. We can get around this by looking at infinite repeating tilings instead, or equivalently, tilings of a torus. Here are the 5 tristicks tiling a 2×5 torus: #18: Excluding (as we must) the “+” tetrastick, the remaining 15 tetrasticks have area 60. Place them on a 5×8 toroidal grid so that every point is connected to three others. (I don’t think the parity issue should be a problem in this context, but I could be wrong. See comments).)

Going back to graph theory terms, what we want is a 3-regular (each vertex has degree 3, that is, it has three edges connecting it to other vertices) spanning subgraph (a graph containing all of the vertices of the original, but not necessarily all of the edges.) A Hamiltonian could be called a 2-regular spanning subgraph, with the added provision that it must have a single connected component. I’m not worried about our solutions breaking into disconnected components in our 3-regular problems here. 3-regular graphs are also called “cubic”, but that term seems confusing in the context of polyforms, so I’ll avoid it.

Another way to make 3-regular spanning subgraphs of a grid is to use a triangular grid. Because corners can connect to three other points, we can use finite sections of the grid this time.

There are 12 tristicks on the triangular grid. The section of the triangular grid in the shape of the hexagon shown below has spanning 3-regular subgraphs with 36 edges. #19: Find a tiling of the 12 triangular tristicks on a 3-regular subgraph of a section of the triangular grid bounded by a convex hexagon with side lengths 2,3,2,2,3,2.

Again, I got pretty close before I gave up; maybe you’ll have better luck. I’m pleased to have a problem that showcases the triangular tristicks. If the square polysticks don’t get the respect they deserve, this is doubly true for the triangular polysticks. Livio Zucca has a page with some triangular polystick solutions, (scroll most of the way to the bottom) but I can’t say that I’ve seen them elsewhere.

Got any other ideas for figures of segments in a grid that could profitably be tiled with polysticks? Any ideas for interesting triangular polystick problems? If you do, please share them in the comments.