Good Will Hunting is a movie about a young genius, played by Matt Damon. In the movie, Damon’s character figures out the solution to a problem that has alluded mathematicians for many years. The problem is find all the homeomorphically irreducible trees such that n=10.
Now this problem really that difficult? Turns out, not really. The most challenging part to most people is figuring out what the problem wants. Well we know what trees are: connected graphs using all vertices but not creating circuits. So it this case, the number of vertices would be 10 as n=10. Now then, what are homeomorphically irreducible trees? Simply put, they’re trees that are actually different(2 tress are the same if one’s difference from the other is a slightly different angle between vertices or a different rotation between the trees), and must not have any vertices with any reducible vertices(those with only 2 lines/edges going through them). So now you can do this problem, it just takes a bit of thinking. The trees at the end should look like these:
There is a certain kind of art behind the graph coloring and the four color theorem. I mean, of course it is because there is actual color being used in a math problem. Math, where usually you have to add and subtract numbers. This painting above, created by Piet Mondrian, does not exactly represent the four color theorem. There are edges touching that share the same color, so that of course would not work in the color theorem. But this painting was done in 1930, and the four color theorem wasn’t approved until 1976. When you compare the oil painting to an actual four color theorem problem, at first glance you might jus consider both of them to be pieces of abstract art. Of course once you take a closer look, you can see that math problem behind the picture on the right. “In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.” So maybe Mondrian wasn’t trying to achieve the four color theorem with his oil painting, but he was getting close. There is math everywhere, even in art. Or sometimes the math problem turns into the art.
Vertex coloring is the simplest form of labelling a graph. “When used without any qualification, a coloring of a graph is almost always a ‘proper vertex coloring,’ namely a labelling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color.”
Also, graph coloring with the most (k) colors is called ‘proper’ k-coloring. Coloring with the smallest number of colors that is needed is called chromatic number or sometimes represented as y(G). ” A graph that can be assigned a ‘proper’ k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k.” Vertices are also classified in same color or color classes, independent sets are formed from such classes.
“Nelson asked: What is the smallest number of colors that you’d need to color any such graph, even one formed by linking an infinite number of vertices?”
The Hadwiger-Nelson problem is a problem that deals with the four color theorem and is it really true for infinite amount of vertices. Aubrey De Grey who is behind this says that it is not possible for four but it is for five colors. When he tried around 20,000 vertices it did not work with four. When he tried even just around 1,000 vertices it didn’t work with four either.
In this article it explains to us the real ways that the Four Color Theorem came to be. In 1976, Kenneth Appel and Wolfgang Haken finally succeeded in approving the color theorem but were unable to prove to others how the Four Color Theorem works without suggesting to draw an infinite number of maps to prove it. The truth of the matter was that proving the Four Color Theorem would only be possible with the help of computers. They used the reductio ad absurdum (reduction to absurdity) method. This states that “If we want to prove that something is true, we instead assume that it is false and show that the rest of math goes bad. That is, by assuming falsity, we encounter contradictions to already known truths.” So, Appel and Haken used this idea along with a computer program to work on any map, assuming that there might’ve been a map out there that needed more than four colors. After the computer proved that no map needed more than four colors to complete the four color theorem became the first major mathematical theorem to be proved using a computer. Who knows if this could’ve ever been truly proven without the help of technology?
In July 1879, Alfred Bray Kempe found the proof for the four color conjecture, he submitted the theorem to the American Journal of Mathematics. Soon after, it was published at the end of that year.
In Kempe’s method, he used an argument known as Kempe Chains. If every region on a map is colored but one, then that point left over becomes X. In the end, if X is surrounded by all four colors, then there is a color left for X to become.
A year later, Percy John Heawood was able to prove Kempe wrong by publishing a paper on map coloring theorems. This proved that every map would be five-colored.
Thinking of all the history involved in Coloring theorems is crazy, years ago they started looking into this and everyone rejected peoples solutions, and then came a computer.
While it’s obvious that math is in all video games, between pixel designs and character stats, it’s also used when finding the best way to grab all of those pesky yet useful hidden items around a game map. While reading this link: https://arxiv.org/pdf/1608.06175.pdf, the Traveling Salesman Problem algorithm was found to be the best way to help players attain items that are scattered around games such as Pokemon, Legend of Zelda, and the game that was used in the experiment done in the article, Far Cry 3. Through using the algorithm, the best routes can be found, either based on time or distance, while also taking into account cut-scenes, obstacles such as drop-offs and climbing, and more video-game attributes that may get int the way of finding the fastest paths.
I found this to be really interesting, even if I’m not one for going on item hauls when I play video games. There are many people called “speed players” who are dedicated to cutting every corner to find the fastest ways to play their favorite games. Knowing just how rapid-fire the play, going into the minutes-range rather than finishing games in hours, they most likely use this algorithm to perfect their strategy. For anyone who likes to play on their XBox or Nintendo DS, do your math!
Two examples of interesting TSP Applications I came across:
The people in charge of creating routes for school buses and bus routes in general use the Traveling Salesman problem to drop off their passengers in the most optimal way possible while bringing the bus back to the original location.
Some Airlines like Southwest use TSP to schedule flight paths so that their crews fly to several different locations and come back to their home airport at the end of their shifts. Other airlines have their planes just fly back and forth between airports which results in a much simpler solution to bring the crew back to their home airport, but also is a less optimized use of resources.
According to this article, bees can solve the traveling salesman problem. THAT’S RIGHT! NOW THE BEES ARE GOING TO RULE THE WORLD! HIDE YO KIDS, HIDE YO WIFE CAUSE THE BEES ARE COMING TO STING YOU!!!
On a more serious note: this is actually interesting. Studies show that the flight of a bee becomes more efficient over time, and that they are continually optimizing their routes over time, becoming better navigators with each flight, changing route sequences to improve speed, and becoming adapt to their favorite flights.
Think about how long it took for us to figure out how long it would take for the current fastest supercomputer to brute force-figure out the shortest possible route. Now that was for 100 different locations. Now think about how many flowers there are, and how often bees travel to them. No wonder researchers also say that in the future when your GPS tells you to go left, you may have a bee to thank for that information.
While doing a little research on the Traveling Salesman Problem, I found a short article in a journal about evolutionary computation. In this specific issue, the author discussed how ants are capable of finding the shortest path from a food source to their nest.
The article explains how, at one point, an ant will have to choose between going right or left. They are ants, so obviously they choose randomly. However, this means that about half of the ants will choose correctly. If, for example, one path is on a downward slope and the other on an upward slope, it is probable that more ants will choose to go down.
Keep in mind, as each ant walks towards its’ food source, they are releasing pheromones on the ground. This leaves a trail for the other ants to follow, which is much like the line segments connecting the vertices in a traditional Traveling Salesman Problem. As each ant travels towards the food source, one of them will find the shortest path, given the number of ants per path.