You and I are no more than 4.57 friendships away from one another.

Over the past hundred years social relationships have evolved, making us increasingly more connected with those around the world in a wide variety of ways.  In this post, I will tell you a story about the connectedness of social relationships, taking us from an early 20th century Hungarian author to an 18th century Swiss mathematician, to one of the largest tech giants of our era, and touch on some cool mathematics along the way.

In an attempt to articulate his observation of the growing interconnectedness within society, in 1929, Hungarian author Frigyes Karinthy famously suggested that any two individuals were connected by 6 friendships, which have been coined “degrees of separation.”  In other words, given any other person, say famous actor Will Smith, you should be able to find 5 other people such that the 7 of you are connected by 6 friendships, as depicted below.

I bring Will Smith up since he starred in the 1993 theatrical version of the famous play “Six Degrees of Separation”, which was loosely based on this notion of social interconnectedness.

Philosophy and media aside, how can we actually mathematically encode and measure social relationships?  The answer: graphs.  First studied by the famous mathematician Leonhard Euler, a graph is simply a collection of vertices and the edges that connect them.  For example, the above picture connecting you to Will Smith is a graph with 7 vertices and 6 edges.  Euler famously used graphs to solve the Bridges of Konigsberg problem.  Since then, graph theory has proven to be a powerful tool to solve many problems.  Google has used graphs to encode the connectedness of websites across the internet, and Facebook has encoded the friendships of their users with their Facebook Friendship Graph.  This Facebook Friendship Graph is pretty straight forward:

A vertex <=>  A Facebook user

An edge connects two vertices <=> The two users are Facebook friends

To celebrate its 12th birthday, Facebook recently set about to actually compute the average degrees of separation between two Facebook users.  In terms of the Facebook Friendship Graph, this amounts to finding the average distance (i.e. minimal edge-path length) between two vertices.  This kind of computation can be done by brute force methods for small graphs.  However, as of the writing of this post, there are about 1.6 billion Facebook users, and they are highly connected.  That means there are over 1018 pairs of vertices whose distance needs to be checked, something that is simply too computationally intensive to do directly.  So Facebook instead used a variety of techniques to statistically analyze this enormous data set, including hash functions, the Flajolet–Martin algorithm, and a powerful graph processing program Apache Giraph.  Check out their blog post below where they explain their methods in greater detail.

Facebook found that the average distance between any two vertices in the Facebook Friendship Graph is approximately 4.57 so, in their language, there is an average of 3.57 degrees of separation between two users.

You can go to their blog and see the average distance between you and a random other Facebook user.  Personally, I am an average distance of 4.15 away (i.e. 3.15 degrees of separation away) from anyone else, confirming my longtime suspicion that I am highly connected.

The new academic year is now well underway and the OU Math Club blog is back.  Behind the curtains, the role of blogmaster for the next year has been taken over by me, Jeff Meyer.  I am excited to tell you about all sorts of fun and interesting math things.  If you know of something that everybody should hear about, email me at jmeyer at math.ou.edu and we’ll get it on the blog!

As soon as I agreed to run the blog this year, I knew exactly what I wanted my first post to be about: tiling the plane. The idea is simple, namely what are the ways one can cover the whole plane by repeating some sort of geometric pattern?

One type of tiling requires you use only a single convex polygon over and over again.  (Recall a polygon is convex if its interior angles are less than 180 degrees.)  I suspect you can find a convex quadrilateral that you can use to tile the plane.  If you stretch or shear your quadrilateral a little bit, would it still tile the plane?  I encourage you to think about this, and maybe try sketching it one a piece of paper.  Sketching tilings is a fantastic way to pass the time in a boring meeting.

So let me now ask you a question: Can you find a single convex pentagon that will tile the plane?

It turns out, this is a really hard problem.

German mathematician Karl Reinhardt in 1918 first came up with 5 ways, and since then a total of 14 had been found. That is until this past year.  Three researchers at the University of Washington, Bothell found a 15th!  They found it after a lengthy computer search.  The algorithm for the search was developed by Dr. Casey Mann and Dr. Jennifer McLoud-Mann and automated by undergraduate David Von Derau.

All 15 known classes of pentagonal tilings, the bottom right being the one discovered by Mann, McLoud-Mann, and Von Derau. (EdPeggJr./Wikipedia)

It is amazing that there are so many open questions here:  Is this the complete list of convex pentagonal tilings? If not, are there finitely many?  Might there be infintiely many?

I think this is such a fantastic story for two reasons.  First, the problem is so easy to state and understand.  You could explain it to grade school students.  Second, this discovery was the result of a collaboration between faculty and an undergraduate.  For all you undergraduates out there, keep in mind there are lots of tangible research questions.  You just need to talk to some encouraging faculty who can help you find one.  If you do, then maybe next year there will be a post here about you!

Take a moment and check more details at the following links:

NPR:

NPR:

The Guardian:

University of Washington, Bothell:

Wikipedia:

What can you do with a million business cards?

Do you have a stack of business cards and you are wondering what to do with them? Well wonder no more! First scan those cards in case you need to reach those people. Then you are ready to build your own (approximation of) a famous fractal: the Menger Sponge.

Who would build such a thing? And how many business cards would you need to build three iterations of the Menger Sponge (aka Menger Cube)? You can find the answers here:

TED Math talks.

TED is a nonprofit devoted to spreading ideas, usually in the form of short, powerful talks (18 minutes or less). TED began in 1984 as a conference where Technology, Entertainment and Design converged, and today covers almost all topics — from science to business to global issues — in more than 100 languages.

Here is a collection of some entertaining and excellent TED talks in mathematics.

http://blog.ted.com/2012/11/21/8-math-talks-to-blow-your-mind/

Enjoy!!

The 2014 Abel Prize goes to Professor Yakov Sinai.

The Abel Prize foundation of Norway just announced the 2014 awardee of this prestigious prize for 2014. Named for the great Norwegian mathematician, Niels Henrik Abel, the prize was established by the Norwegian government in 2001 with an endowment of 200 million Norwegian kroner. This allows for an annual award of 1 million U.S. dollars.

The winner this year is Professor Yakov Sinai of Princeton University and Landau Institute of Theoretical Physics of the Russian Academy of Sciences for his beautiful and enduring work in the areas of dynamical systems, ergodic theory and mathematical physics. Here is the link to the Abel Prize page along with more information about Professor Sinai’s work:

http://www.abelprize.no/c61094/seksjon/vis.html?tid=61095&strukt_tid=61094

Niels Henrik Abel was one of the great mathematicians of the nineteenth century and like some of that era suffered a tragic end. He solved the ancient and deep problem of showing that there cannot be a formula to determine the roots of an arbitrary quintic polynomial with integer coefficients. Sadly, by the time his results were understood and appreciated, he succumbed to consumption at the young age of 26. Here is a complete biography:

http://www.abelprize.no/c53672/seksjon/vis.html?tid=53910

What is beauty? ‘Tis but a pleasing formula…

A beautiful formula from Euler’s beautiful mind.

At long last, here is some evidence of something that most mathematicians would say they have known a long time: apparently equations, especially pleasing ones, are perceived as art in a mathematician’s brain. Here is the link to the article in the Scientific American.

http://www.nature.com/news/equations-are-art-inside-a-mathematician-s-brain-1.14825