Building Transport Systems Through Graph Theory

While doing a little research on Graph Theory I found an interesting connection that we’ve already touched upon in class. While the Bridges of Konigsberg were a simple example of Graph Theory, there are many other complicated transport systems that have been built on the foundation of this same theory.  This article, in particular, brought up the use of telecommunication systems as networks that would need specific links, like cables, in this case, to connect the “nodes”. The article really strips all of the information back to the basics, so it is extremely easy to understand. It’s a pretty short read as well, so if anyone is at all interested in this kind of thing, I’d definitely recommend it!

The Art Gallery Problem – Helping Heist Movies and D&D Campaigns Alike

Sure, George Clooney is a good-looking man but did he consider the art gallery problem in Ocean’s 11? …No seriously, I have no idea. I’ve never seen the movie. 🙁

I was curious about graph theory and what prominent topics are involved in it. Perhaps one of the most interesting and practical problem I found in the Wikipedia entry for graph theory is the art gallery problem (also see here).

To sum it up: The problem asks us to consider how many security guards we’d need to carefully monitor an art gallery. This depends on many variables such as the size and shape of the art gallery.

Marianne Freiberger for Plus Magazine, summarizes the mathematician S. Fisk’s answer to this conundrum as:

..[Y]ou never need more than n/3 guards (so that’s 9/3 = 3 guards in the example in the figure). That’s true for any simple polygon with n vertices, no matter how complicated and irregular it looks.”

Which is pretty amazing.

So next time you’re watching your favorite heist movie or thinking about starting a heist campaign in D&D, consider the art gallery problem!

Graph Theory in Chemistry

I found a page of a book written by a Romanian organic chemist. This page mentions how chemists use graphs like the ones we used in class to demonstrate covalently bonded compounds. After reading this page, I remember doing something very similar to this in my high school chemistry class. The edges of the graph represent covalent two-electron bonds and the vertices of the graph represent atomic cores (valence electrons are not included in these graphs).


While looking up gerrymandering I came across a site that showed how the U.S looks before and after the county lines were distorted. I found this interesting because you can see how much influence State legislatures have in decided the districts. The picture i added shows the difference between the original county lines and after when they were changed to lean left or right.


I also remembered watching a John Oliver episode about Gerrymandering and though it was very interesting to see the affects. It is 20 minutes long but it is kind of funny and flies by. Please watch .

Sealed Bidding with United Airlines

“Auction overbooked airline seats” was an article that was written a year ago when United Airlines had the incident of dragging a passenger off the plane because more passengers showed up for the flight then there were seats available. The author of this article suggests a method that allows passengers to volunteer their seats at check-in. He suggested that sealed bidding method would be the best way to entice passengers to give up their seats if they chose. If they bid the lowest then they will give up their seat, but will get compensated and the airline would arrange other travel amenities. This will help show what each passenger believes is the best value of their seat, as well as bring in more bids for the airline so there is less of a chance for the airline to get overbooked on a flight.


Approval Voting in US elections

I came across an article that talks about how presidential elections should be held by using approval voting. Currently, our voting process consists of citizens individually voting for who they want to win, then the Electoral College in each state votes based on the votes that state received for each candidate; in order to win, the candidate must receive the majority of electoral votes. This system of voting has been used for a significant amount of time, but whenever a large portion of voters disagree with the outcome, the topic of changing the voting system to make it “more fair” is discussed. My understanding of this voting method is that each election has different outcomes, it does not favor one party over the other, however, it does make it extremely difficult for a third party candidate to win a states electoral votes.


Changing the voting method to approval voting does not seem like it would be the best option to me, although this article thinks otherwise. The article talks about how the plurality method is a “really bad” method to use and how approval voting gives candidates a more equal opportunity to win. As we learned in class, the plurality method does not satisfy two criterions—the Condorcet criterion and the IIA criterion. However, I do not believe changing to the approval voting method would be the most effective change. The approval voting method does not satisfy the majority criterion or the Condorcet criterion. This means that both methods only satisfy two out of four criterions in Arrow’s Fairness Criteria.


If people are arguing to use the most “fair” option of voting, it seems as though Copeland’s Method should be their method of choice. This method meets the majority, Condorcet, and monotonicity criterions. It would be considered the most fair because it meets three out of the four requirements on Arrow’s Fairness Criteria.


It is interesting to me that people decide that the method for voting should change when they do not like the outcome, yet when their candidate wins, they are happy with the method. There is no perfect method for voting; therefore, there will rarely be an outcome where everyone is happy. It is interesting to compare different methods and their outcomes in elections because ultimately, depending on the method it is possible to get a different winner each time a different method is used. For now, I personally believe that we should keep our voting methods the same and educate ourselves more on how we vote and who we are voting for in order to try and better our political system with each election.

The link to the article is below incase you would like to read it.

How optimally compacted districts should replace drawn districts

Looking at the image below, this shows how drawn voting districts should be replace by optimally compacted districts. The reason being that it makes the voting a more accurate representation of the trends. The state legistator and majority party of the house are the ones who decide the voting districts and essentially “cut an arbitrary line” through the state.  The division of the states, allows for the “losing side” to still have enough districts to potentially win.

Sealed Bids and Realtors

Sealed bids are used frequently when it comes to selling real estate. Brokers have been turning to the sealed bid auctions as the economy has decreased. It is  a way for the brokers to get people more interested in buying houses rather than the conventional way. The seal bid creates a buzz on a property and in return more people become interested in buying it.

Auctions like this were popular in the boom years and in recent years have  become a way for people to sell their property quickly. “In contrast to today’s sealed-bid auctions, those of the boom years typically were used to help organize a pre-existing bidding war and often didn’t have a minimum bid or a contract.” When doing a sealed bid auction today the rules are much different.

Sealed bid auctions require potential buyers to submit their bids by a certain time. They must submit them in writing to the seller. Then seller will choose which bid they prefer the most. In some cases all the bidders had to pay a 10% deposit, all the bidders who did not win got that deposit back.

This kind of process when selling and buying a house is pretty interesting. In some cases it could go badly for the buyer. If they were moving for work ect. and trying to get rid of their property quickly, and decided to use this sealed bid auction approach, they could potentially not get as much for their property as they had hoped.  On the other hand if the property is in a place like New York City and there are a few potential buyers, a sealed bid auction might be good because then the buyers might bid more for a need for that property. “Sellers who want to wring every last cent of their home’s value from the purchase may prefer the traditional sale process, which allows them to play bidders off each other to increase the price.” In other cases the sealed bid auction might be the best choice for them.


Selling with sealed bids

What are states doing about Gerrymandering?

This article is about how states are not waiting for the supreme court to fix gerrymandering. Ohio is one of the most gerrymander state and have come up with a way that the minority has more say in the district lines. Some states have even used citizens’ initiative petitions to stop gerrymandering.

This image the gerrymandering lines in Ohio. These districts are obviously very altered from what they were supped to be.


This is actually what America would look like without gerrymandering!

In this article by The Washington Post it explains how gerrymandering can be optimized in the US. It includes an interesting topic of how to fix the biased assortment in the district assortments. Instead of allowing people to draw the lines we can instead program a computer to draw the lines out for us. The computer program is able to compact the population much more orderly than any other decision made by man. It is so accurate that it is able to reflect actual neighborhoods and homes in that neighborhood to be perfectly divided. The most interesting part is that this article also includes pictures to compare how we divide the US in our current congressional district map to the computer drawn map. It is easily seen that the computer drawn map seems much more optimal both in order and compactness. So what do you guys think, would this computer drawn map be a better option than the current mess that is the US’s district map?