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.degrees

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.

https://research.facebook.com/blog/three-and-a-half-degrees-of-separation/

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.

facebookgraph

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.

Happy 200th Birthday George Boole!

Today (November 2, 2015) is the 200th Birthday of the mathematician George Boole.  To celebrate, here is a fantastic song and video created specially for this occasion.

“The Mathematician – The Bould Georgie Boole”
Performed by The Arthur Céilí Band, featuring Jim Flanagan & Mike Simpson

You can also download the song so you can listen to it all the time here:
https://arthurceiliband.bandcamp.com/track/the-mathematician-the-bould-georgie-boole-radio-edit

Besides being a lot of fun, this song and video is a great little biography.  Of course, if you want more info, you can check out George Boole’s Wikipedia page:
https://en.wikipedia.org/wiki/George_Boole

George_Boole_color

That being said, there is one story I would like to point out here.  George Boole worked in many areas, but perhaps the most important area today is what we now call Boolean algebra  (https://en.wikipedia.org/wiki/Boolean_algebra).

Introduced by Boole in the around 1850, it was not until the 1930’s that an undergraduate at the University of Michigan named Claude Shannon realized this hitherto abstract theory could be applied to electromechanical relays.   Shannon went on to write a master’s thesis on this topic at MIT.  Since then Boolean algebra has become the basis of digital circuit design.

Here is my challenge to all you undergraduates out there: can you make a connection like Shannon and use a seemingly totally abstract mathematical theory to model some real world phenomena?  Maybe you too can make some revolutionary discovery!

OU Math Movie Night: A Beautiful Mind

I am excited to announce the first OU Math Movie Night.  This Thursday, we will be showing the critically acclaimed “A Beautiful Mind” in honor of John Nash who passed away earlier this year.  This event is open to everyone, so invite your friends to come watch this movie.  Afterwards we will have an informal discussion of game theory.  Here are the details:

When: Thursday, October 22, 5:30-8:00pm

Where: PHSC 1105

What: Movie, Food, and Math!OUMathMovieNight_Oct_22

 

Career Opportunities This Wednesday

Depending on your interests, there are two great career opportunities this Wednesday, October 21st.  Two companies, BP and OMRF, are interesting in telling you about themselves.  Plus, at both events, there will be PIZZA!

First, Math Club will have a BP representative.  Here are the details:

When: Wednesday, October 21, at 5:30

Where: PHSC 1105

What: BP Representative & FREE Pizza

mathclubOct21_2015

Second, OMRF, nonprofit biomedical research institute, is also interested in Mathematics students. Here are the details:

When: Wednesday, October 21, at 5:30

Where:  Ellison Hall 132

What: OMRF Representative & FREE Pizza

RecruitmentForm10-2015[1] (1)

First Math Club Meeting of The Year

Come one, come all! This Wednesday is the first meeting of the OU Math Club.  This is an organizational meeting, so be sure to show up to help plan out activities for the rest of the year.  Plus, if that is not already enough, there will be pizza.

Here are the details:

When: Wednesday, October 14, at 5:30

Where: Math 209 (a.k.a The Math Center)

What: Organizational Meeting & Pizza

mathclubOct14_2015

PCI Looking For Interns

PCI is a Norman based company that offers asset optimization solutions for power generation and trading companies. They are keen to hire people with a math background for internships. PCI is currently hiring for both regular and paid internship positions and will have Hiring Managers and different employees from different teams presenting and mingling with students after each session.

Date: Wednesday, September 23, 2015

Time:  10:30 am – 1 pm

Location: Frontier Room, 2nd Floor in Oklahoma Memorial Union Building

image004

Pentagonal Tilings and Undergraduate Research

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.

pentagontilings15.svg-copy_custom-ac24ad7176f459ff08d3816abc7fbffdcfdb60a7-s1600-c85

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: