## Knights Path

I found our discussion in class about a knight’s path very interesting. What I like the most is how intricate the designs are if you trace the path completely. We looked at some of these in class, but I found some more online. Going into the class, it seemed like such a simple thing. I didn’t really think about how much the knight piece would have to move in order to land on every spot on the board. But, looking at the designs on this website just shows how intricate and complex it is. I used to play chess a lot with my mom, and so when I got home I was able to talk about all of this with her. This was probably my favorite topic so far.

Here is the website I’m talking about.

http://mathworld.wolfram.com/KnightGraph.html

## My Father’s Take on Graph Theory

The day after our class I showed my dad the picture of the bridges and explained what the rules were. He sat for twenty minutes, just to express that there could be no way.  He had never seen this problem or heard of graph theory. Despite this fact, he had a clever opinion on the bridges. As long as there are an odd number of bridges with each bridge having one way onto the bridge and one way off the bridge, there would need to be five points the bridges connect to, instead of the original four. This is due to one point being the start and the others wrapping around the other four points. I’m not sure if this is one hundred percent true but it was nice to see someone who had never experienced this type of theory put his own take into it.

## Graph Theory and the Ramsey Theory

After our last class, I was curious to see if graph theory could solve any other forms of problems. After a little digging, I found the Ramsey Theory. The theory was named after Frank Plumpton Ramsey, who had spent all 26 years of his life devoted to it.

A typical result in the Ramsey  Theory states that if some mathematical object is partitioned into finitely many parts, then one of the parts must contain a subobject of an interesting kind.

He is most known for his dinner party problem, which is to find the minimum number of guests that must be invited so that a certain number will know each other and a certain number will not know each other. I was very curious to see what that problem would look like, so I did a little more research. This is what a completed graph for the problem looks like:

Each letter/vertice represents a guest, the blue lines represent guests who know each other and the red dashed lines represent people who don’t know each other. This little animation shows the number of triangles that are formed using lines of the same color. The number of triangles will be the minimum number of guests that need to be invited.

More on Dinner Party Problem:

http://mathforum.org/mathimages/index.php/The_Party_Problem_(Ramsey’s_Theorem)

## Proving Something Impossible

I’ve always been taught, at least in science, that nothing can ever actually be proven possible or impossible. It can only have or lack support in its viability. However, it seems that in the world of mathematics, that’s not always the case. Things can in fact be proven possible or impossible, and there are new theories being created constantly that can do just that. That thought occurred to me when we went over Graph Theory, and were able to mathematically prove that the Seven Bridges of Konigsberg was an unsolvable problem. The fact that we could not only prove it was impossible, but also do it so simply and easily in a graph, was astounding.  I’m still a biology major, and cells and microscopic organisms are still my greatest interest, but being able to 100% prove or disprove something will always be fascinating to me.

## Social Network Analysis

When it comes to graph theory, I was trying to find different maps that show trails or streets that I could further describe in detail because that was all I was thinking of to explore while considering the topic of this blog post.  Upon further research, I found that graph theory is not limited to maps and roads by any means, it can be found in a variety of examples using things we use in our everyday lives.

I researched multiple different real life applications of graph theory on a list on this website (if you would like to see more real life examples that I don’t discuss you can find it here):

https://www.quora.com/What-are-real-life-applications-of-graphs

However, the most interesting example I found was regarding social media.  The website describes the application of social media to graph theory as: “Connecting with friends on social media, where each user is a vertex, and when users connect they create an edge.” This sounded like a topic that was worth diving a little deeper into, since social media plays such a huge role in our lives.

I paraphrased that sentence and found that this real life application to graph theory is called “Social Network Analysis” or SNA.  This is described as being the mapping of relationships between people via different social networking websites, or different inanimate objects like computers, or even URLs.  The nodes in the network are defined the people in the groups, while the links between them show a mathematically visual flow of their relationships.  When it comes to computers, the nodes would be the computers themselves and the links would be the invisible connection each computer or smart device has when communicating signals back and forth.  Below, you will find a visual that shows an example of a Social Networking Analysis:

This network above in particular is known as a “Kite Network”, which was developed by a researcher named David Krackhardt. On the side bar to the right in the image, you can see the Degrees, Betweenness and Closeness information.  These are defined as the three different “Centralities” of the image.

The Degree Centrality is the number of direct connections each node (or person) has.  As you can see in the image, Diane seems to have the most connections.

The Betweenness Centrality is all about having few direct connections, but having the nodes you are connected with be some of the most popular.  In the image, Heather has very few connections, but she is between two very important nodes in the network.

The Closeness Centrality is having very short paths to others, like Fernando and Garth in the image above, but the pattern of their ties allows them to connect with everyone in the network anyways so they can be closer with fewer nodes.

Although this network seems to be neither a circuit nor a path as far as i can tell, (because of the line protruding from the side of the shape, slightly throwing it off) all of the connections are still meaningful because they are between people who created relationships with others and are making more relationships because of the never-ending flow of the social media network.

If you would like to learn more information on this topic, you can visit this website:

http://www.orgnet.com/sna.html

## Euler path in Sports Fields

Last class, we talked a lot about Euler’s paths and Euler’s circuits.  After thinking of places I might see this in real life, I began to think about how almost all sports playing fields use some type of boundary lines to keep the game “in play”.  The first field I thought of is a Soccer field.  I realised that there were many more than 2 odd vertices on this soccer field, but attempted to make a circuit anyways.  It did not go well, as expected.

This field clearly had too many vertices and edges for it to possibly be a Euler’s circuit.  After taking a closer look, I saw a way that a watered down version of a soccer field could be a Euler’s path.  This time I traced a much watered down version of a soccer field, and once again did not find a Euler’s Circuit.  What I did find was just as magical though; I found a Euler’s Path.I couldn’t find any details of Eulers Paths and Circuits in sports fields, but it’s nice to know there’s some math going on everywhere, even on a soccer field.

## The Many Paths on a Pokemon Journey

As a kid, I shared the dreams of many: to become a Pokemon master. Although I can’t say I ever achieved this goal (because they keep making hundreds of new ones every year), one thought that came to mind after today’s class was the many routes in each region of the game that connect cities and towns to more cities and towns.

As the games have progressed, we’ve seen a drastic improvement in the overall layout of each region. Here below is the Kanto Region, in all of its glory:

And now, a map of the Kalos region, in a game released around twenty years later:

There are seven regions to choose from in the mainstream games, but personally I found that Kalos has a beautiful array of plots and lines to analyze.

Below is a more linear image of Kalos from Serebii.net, where you can see clear paths from one destination to the next. In math terms, a blue or orange dot represent the vertices here, and the white routes are edges:

Now for the big question: Is there a Euler’s Circuit or path in this Pokemon region? Unfortunately the answer is no, I found at least four or five odd degree vertices here. On another note, I couldn’t find a Pokemon region that was fully connected (that is, because there are often islands within the game for players to sail to).

The region which I believe does contain a Euler’s Path would be Generation V’s Unova, which as you can see below should have (if my counting is correct) exactly two odd vertices:

Did you guys find this post interesting? Am I off regarding how graphing theory works? Let me know in the comments below! Thought it’d be cool to reference one of the greatest series of RPGs out there.

Sources: https://bulbapedia.bulbagarden.net/wiki/File:Unova.png, https://imgur.com/r/all/kCiUIuE, https://www.serebii.net/pokearth/kalos/, https://bulbapedia.bulbagarden.net/wiki/File:Kanto_Town_Map_RBY.png

## Graph Theory and Google

After doing some research, I was quite shocked to find out that graph theory is correlated with one of the most popular search engines many of us use on a daily basis; Google.

Relating to what we talked about in class today with graph theory, pages on the internet are linked to each other by hyperlinks; each page is a vertex and the link between two pages is an edge.

According to a blog on Cornell University, the Google Search Engine is based off of one simple algorithm called “PageRank”, which is based off of a simple graph.  “The PageRank graph is generated by having all of the World Wide Web pages as nodes and any hyperlinks on the pages as edges.” (Cornell University).

Specifically, the edges are characterized by being either week or strong. Pages that are linked by more credible services (Fox News, USA.gov) have higher weightings, which makes them more credible. “The total number of edges also plays a role as pages with more edges tend to have better ranks” (Cornell University).

Let’s say you search for “Tumblr”. The search engine parses the strings and then tries to find the sites that have similar strings. It then ranks those sites by using PageRank with the best ranks listed first. This is the exact reason why when you search for “Tumblr” the first link that comes to the page is the official Tumblr page; Tumblr is a notable and popular website, meaning it have high ranks.

Google will adjust the weighing system in order to keep it as confidential as possible. There have been a few instances where people actually came close to figuring out the system. To keep this from happening, Google cautions that any website that is caught manipulating the system will will be manually devalued in violation by Google.Google’s edge weighing algorithm is meant to be kept confidential, and I personally would have never guessed that graph theories were involved with Google. But, after reading this information and when you think about it, it makes perfect sense.

The same goes for Google Maps. “The entire premise of Google Maps is using a big giant graph with nodes and edges to figure out fastest or shortest way to travel” (Cornell University).

In this graph (not to scale), each node is a city and each edge in the graph represents a path.

Math is behind the most innovative technology created today.

Sources:

PageRank: The Graph Theory-based Backbone of Google

Google Maps–it’s just one big graph

## Chess

Considering we are allowed to elaborate on any topic related to class, I have chosen to look more into the game of chess. Chess is not something I have an interest in playing, or have played growing up. I didn’t realize how mathematical the moves were until it was brought up in class the other day.

It then got me thinking about when we were talking about the voting methods, and the number of candidates determined the number of possible combinations. This can be true with a game of chess to, which also was relating to what we did today. I am talking about when we were given the worksheets and had to make it around the board passing each square once but never going back the same way. There is a trick to it. This then ties into the vertices and edges topic, then connecting lines which where you moved on the chess board and it looks like a big web.

I found some cool chess facts, that made me realize how mathematical this game really is.

1. There are 400 different possible positions after one move each. There are 72,084 different possible positions after two moves each. There are over 9 million different possible positions after three moves each. There are over 318 billion different possible positions after four moves each. The number of distinct 40-move games in chess is far greater than the number of electrons in the observable universe.
2. According to the America’s Foundation for Chess, there are 169,518,829,100 ,544,000,000,00 0,000,000 (approximately 1.70×10 29) ways to play the first 10 moves of a game of chess.
3. The longest chess game theoretically possible is 5,949 moves.
4. The first Chessboard with alternating light and dark squares appears in Europe in 1090.

To me, this is crazy that there are this many combinations of possibilities just depending on where that first person makes their move, and the rest of them after that. There kind of is no right or wrong way, and I am sure each person sees advances differently than the next. Each game must be so incredibly different from the last one played by the same person.

Just like at the beginning of this course, Donald told us that we would see math everywhere in everything. After realizing how math related a “board game is”, it makes sense that it is all around us in a lot that we do.

https://www.chess.com/blog/keshushivang/interesting-chess-facts2

https://www.chess.com/blog/keshushivang/interesting-chess-facts2