P versus NP lecture, a good place to start on winning $1 million

Here's a lecture, sponsored by the Clay Mathematics Institute (yes, the folks who put up $1 million for the solution of any of the remaining six Millennium Problems) by MIT professor, Michael Sipser.  Not claiming this is a walk in the park, but it's an excellent introduction to what is considered the most accessible of the prize problems, as well as to the vital subject of computational complexity theory. The solution to the P versus NP problem would have many important consequences.

  

Hexaflexagons and other Flexagons

Here is the webpage with a host of resources for today's activity, including links to Vi Hart's videos that got us going.  Have fun and have a great break. I will see you in January and expect that you'll be bringing us hexaflexamexifood.

Update: here is an interesting, somewhat relevant resource: you can make calendars for the new year on various polyhedra and other 3-dimensional shapes. Everything you need is there to print, cut out, and assemble. Enjoy!

December 11, 2012 - Art Gallery Problem => Math Works!

A Challenging Art Gallery

Nothing is more intriguing (to me, at least), than a recalcitrant example of a math problem I thought I had mastered but which refuses to cooperate. In our recent work on graph theory, we had looked last week at a family of related problems called "art gallery problems." We worked through the thinking that led to Fisk's constructive proof of the "art gallery theorem" that Chvatal had proved through more formal (and difficult to understand) means on a few years earlier. Fisk demonstrated precisely how to calculate and arrange the minimum number of "vertex guards" in a polygonal art gallery so as to "cover" the entire interior of the gallery. In simpler terms, this means finding the minimum necessary number of stationary guards placed only at vertices of a simple (non-intersecting) polygonal-shaped "gallery" so that every point inside or on the interior walls of the gallery are in view of at least one guard. We could test such an arrangement by drawing a straight line that stayed entirely inside the gallery between a given point and at least one vertex guard. If such a line exists for every point in the gallery, we have "covered" it and all the art works on the walls or "free standing" (e.g., sculptures, mobiles) are protected 

As I said in a previous post, this number can be found by taking the integer portion (or "floor") of n/3, where n = the number of vertices (or edges) of the gallery. The resulting number is the smallest number of guards that are sufficient for a given gallery and also the smallest number necessary for a "worst-case" arrangement of n vertices. Fisk showed that by triangulating the graph, it is always possible to have n - 2 triangles created by adding n - 3 diagonals connecting vertices which stay completely inside the figure. 

As the above graph has 20 vertices, the floor of n/3 is 6. So 6 vertex guards are sufficient. But are they also necessary or are fewer possible (because it turns out that this is NOT a worst-case for 20 vertices)? 

Assuming we have triangulated correctly, we proceed in Fisk's method by doing a proper (minimal) graph coloring of the vertices (so that no two vertices that are connected by an edge have the same color). Since we have nothing but triangles, it should always be possible to do this with exactly 3 colors. We then count how many vertices have a given color, and whatever the minimum-appearing color turns out to be is where we should place guards.

When we worked on the above-pictured gallery last week, I found a triangulation and coloring for which two colors appeared six times each, and the third color was used seven times. Since six was the number the formula produced, I assumed that this was indeed a worst-case scenario.

However, Taylor pointed out that he placed guards at five of the vertices and could (apparently) "cover" every point in the gallery. This was very strange. If the math worked, then something was wrong. One possibility was that Taylor only thought he had every point in the gallery covered with his five vertex guards, but really there was at least some tiny area that they couldn't cover. Unfortunately (for me), I couldn't see any way that this was actually the case. In fact, it seemed that his five guards were sufficient. And that meant only one of two things: math doesn't work, or I had not found the best way to triangulate and/or color the graph. 

I left the problem "unsolved" over the weekend with the thought that this was an opportunity for the students to grapple with a seeming paradox and to find out if math does indeed have to make sense (at least in this case). In all honesty, I was convinced that I was just stuck in a visual rut and that one or more students, looking with fresher eyes and a more flexible mind, would figure out something that satisfied both the obvious fact that Taylor was right and that the algorithm makes sense. 

Students worked diligently on finding a better way to triangulate and color this gallery. Some found clever but, it turned out, flawed solutions. One easy way to check if the triangulation and coloring are correct is first to see if the resulting triangulation uses exactly 17 diagonals to form 18 triangles. Second, there must be a total of 20 vertices in any coloring. It was this last criterion that showed the mistake students made in trying to draw a "continuous" straight line between the bottom point (labeled 6) and, say, point 20 and point 9. But that is NOT a straight line, as can be seen clearly above. Rough sketches sometimes mask this point. 

A very careful check of the graph above, however, shows that everything is correct. We have exactly 18 triangles created with exactly 17 diagonals, each of which connects two vertices  and none of which is ever external to the polygon. And this better triangulation than mine allowed this student to find a coloring for which, as indicated, only five vertices needed to be colored orange, while six are blue and 9 are purple. The total of 20 is correct, and checking the triangles, no connected vertices have the same color. And so Taylor's informal arrangement of 5 guards, while not unique (his placement differed from the above), was indeed minimal and correct. 

I still have to check a few other student papers, but the one I've shown here was done by Denali. I thank her for pulling my chestnuts out of the fire and proving once again that mathematics makes sense. 

Catching Up

An "art gallery"

Sorry for the hiatus to those who've been following this blog. We've been reveling in the wonderful world of graph theory for  the last few weeks and will be wrapping this up tomorrow and getting back to our textbook, since the necessary manipulatives have arrived, allowing us to move forward to section 1.3 & 1.4.

Meanwhile, things we've explored: the nature of and criteria for Euler paths and Euler circuits, and some real-world applications thereof. From there, we moved on to graph-coloring, one of my favorite topics in all of mathematics because of its many intriguing applications for solving real-world and abstract problems.

First, we looked at how to use proper graph coloring (finding the minimal number of colors necessary) for maps. We explored maps of Australia, the southern part of Africa (some students also did the entire map of Africa), and South America. Students saw how doing a proper graph coloring always led to ways to color a map with either three or four colors so that no two countries or states that share a border   (not a single point, as is the case in the "Four-Corner" US states in the far west) have the same color. An important requirement is that the territories in question must be continuous, so that Michigan, which has two main separated pieces, has the potential to violate basic conditions. We spoke about the famous Four-Color Map Theorem, finally proved in 1975, that shows that in fact there can be no map following the rules that requires more than four colors. We also talked about the 3 Utility Problem and watched a video by the young British mathematician, James Grimes, that offered an ingenious 3-dimensional proof of the impossibility of solving this problem that is grounded in Euler's beautiful formula for the relationship between the edges, vertices, and faces of a certain class of polyhedra. The proof helps explain why the Four-Color Theorem is true, though it is not a proof of that theorem.

We next looked at conflict graphs. These are similar to graph coloring for maps, but unlike the case there, there is theoretically no upper limit to the number of colors necessary to do a proper coloring of a conflict graph. Our examples included finding the minimum number of secure (and costly) cabinets needed to store a set of 7 chemicals where certain chemicals cannot be safely stored with certain others, and the minimum number of cars needed to take students on a trip to a museum when certain students cannot ride "safely" with certain others. Other classic examples (that we didn't look at) include scheduling final exams so that no student has to be in two or more exams at the same time. This is a very real issue that schools face every term, and the software used to figure this out is all grounded in conflict graphs.

Our final exploration in graph theory began today as we looked at a family of related problems called "Art Gallery problems." The picture at the top shows the graph for a theoretical art gallery with paintings on all the inner walls. The rules require that the gallery be a simple (but not necessarily regular) polygon, which means all walls must be straight lines, and walls may only adjoin/intersect at end points: no "bow-tie" shaped art galleries. In the basic problem, guards may be placed only at vertices and may not move (fixed vertex guards). The assumption is that any painting not in view of a guard will be stolen, and the task is to A) determine the minimum number of guards necessary to "cover" (that is, keep in view) all of the inside of the gallery, and B) determine a workable placement of that number of guards. The solution is generally not unique for B, but the solution for A for a "worst-case" gallery with n vertices is unique. The formula is floor(n/3), where the floor function gives the largest integer less than or equal to x (the real number inside the parentheses). So for n = 3, 4, & 5, it is possible to cover any n-sided gallery with 1 guard (note that, for example, n/3 is 1.67 and floor(1.67) = 1). For n = 6, 7, 8, no matter how convoluted our gallery, 2 guards suffice.

The method for actually placing the guards is to triangulate the interior of the graph of the gallery. This is guaranteed to create n - 2 triangles by adding exactly  n - 3 interior diagonals (a fact that has already cropped up in our problem from several weeks ago of creating a "complete graph" on an n-sided polygon). After the graph is triangulated, we perform a proper graph coloring on it. We then count the number of vertices for each color. Whichever one(s) have the minimum number tells us the MAXIMUM number of guards that is NECESSARY, and by picking any one of the colors with this number, we have a valid placement for the guards: just put one at each vertex of the color in question.

Tomorrow, we'll apply this to some worst-case scenario galleries, then look at some of the countless art gallery problems that have emerged since the problem was first posed at Rutgers University in the 1970s. This branch of graph theory is continuously growing, with conferences and journals dedicated to the subject. Perhaps you can speak with your child about some of the problems we look into tomorrow. Maybe some of our students can craft original problems or find new solutions to existing ones. We already have one student thinking hard about the remaining six Millennium Problems, the solution for any of which carries a prize of $1 million.