Good Luck with Finals!

This one goes out to everyone studying related rates problems this weekend for Dr. Kujawa’s and Dr. Martin’s Calc I classes:

Part Time Job Opportunity in Norman!

Dr. Lifschitz passed along this job opportunity here in Norman. If you’re interested, give Mr. Damiani a call to learn more.

My name is Joseph Damiani and I work for TeachPro Tutoring and I was given your number by Carly Shaw who is one of our tutors.  We are hoping you know of someone that is a Math major that could tutor in upper level Math.  Our particular focus would be in Algebra I and II and possibly Geometry.  If you have anyone that is looking for a part time job in tutoring in Norman please send them my way at 330.6299 ext. 113 or my cell at 657.0008.  Thanks.

   Joseph Damiani

   Human Resources

     Phone: 855-ALL-READ (855-255-7323)

     Direct Line: 405-330-6299 ext. 113

     Fax: 405-608-0769

     www.teachpro.net

Winner of the March PoTM

Better late than never, we wanted to tell you that the winner of the March Problem of the Month was Laurence White.  Congratulate him when you see him!

Don’t tell Laurence or Dr. White, but people named White are always trouble :

Maybe things would have gone better if Joe was a mathematician and/or listened to Mr. White:

Joe: He was the only one I wasn’t 100% on. I should have my f****** head examined, going on a plan like this when I wasn’t 100%.
Mr. White: [shouting] That’s your proof?
Joe: You don’t need proof when you have instinct.

2013 PRiME: Purdue Research in Mathematics Experience

Dr. Martin let us know of a late breaking summer research experience.  Purdue University will be hosting an REU this summer called PRiME (Purdue* Research in Mathematics Experience).  It will be a group of 6-8 students lead by Dr. Edray Goins.  The group will work on problems in number theory.  For all the details, you can go to the PRiME website.  The main thing to know is that the application deadline is

this Friday, April 26th!

Another Prime research group working to solve hard problems!

* It’s a good thing it’s not at Clemson, Georgia, Kansas!

Party! Party! Party!

End of the year Math Club Party! Congratulate our departing seniors! Share your summer plans with your friends! Participate in fun math games and partake in pizza and cake!

It’s this

Wednesday, April 24th at 5 pm in PHSC 1105!

A Better Idea

As always, Free Pizza! + Free Cake!

Problem of the Month: Examples Needed

The Grand Poobah of the Problem of the Month has unleashed a new Problem.  You can read the problem (and the rules) at the Problem of the Month webpage. It’s all about finding a certain bounded function.

If you can’t get enough of math pun comics, you’ve got to check out this webpage!

Don’t tell him, but we think the Grand Poobah of the PotM has bounded rationality.

Euler’s Birthday!

Unless you’re that one person who uses Bing, you probably noticed that today’s Google doodle is in honor of Leonhard Euler’s 306th birthday:

Happy Birthday Euler!

If you look closely, you’ll see shoutout’s to Blog favorites like the Euler Characteristic, Euler’s Formula, and the Königsberg Bridges Problem (which was when Euler simultaneously invented topology and graph theory!).

Math Graffiti

The artist Aakash Nihalani has a great outdoor art series in NYC called “sum times”.  Here’s one example:

and another:

and a work in progress:

The artist at work.

For more go here.

Summer Research in Denton

The fine folks at UNT in Denton, TX have a summer research program for undergraduates.  They just let us know that they especially interested applications from OU students and other non-UNT students.

Applicants selected to participate will receive a stipend of up to $2,000 in addition to valuable hands-on mathematics research experience under the supervision of a UNT Department of Mathematics faculty mentor.

Following is the link to the dedicated webpage for the program which provides information about this year’s faculty mentors and research opportunities as well as a link to downloadable .pdf for the attached flier  http://math.unt.edu/2013-rtg-sums

The application form has not yet been finalized and posted, but is expected to be available online soon.  In light of the fact that this year’s deadline is particularly tight, there is an deadline for non-UNT Denton students has been extended to 5 PM, Monday, April 15, for non-UNT Denton students, but interested students are encouraged to submit their applications as early as possible.

If you happen to live in the DFW area, this is a great opportunity for an interesting summer research experience right at home.  Check it out!

Robots vs. Math

Earlier this semester an OU math professor, Dr. Murad Özaydin, and a former OU grad student, Dr. James Dover (now at Cameron University in Lawton), posted their most recent paper on the ArXiv.

It is entitled “Homeomorphism and Homotopy Types of Restricted Configuration Spaces of Metric Graphs”.  But really, as Dr. Özaydin explained in the topology seminar, it’s about Robots on Rails.

As part of our very occasional postings on research in the OU Math department, we wanted to tell you about their very cool theorem.  Before we do that, let’s talk robots.

In real life, robots which can move are often only allowed to move along certain paths.  They might actually move along rails; or, even if they just drive along on wheels in a factory their programming steers them along certain fixed paths so they don’t accidentally run into walls, expensive machines, people, etc.

And even non-robots often travel on real or virtual rails.  Trains, of course.  But cars on the freeway system, planes flying through the air (commercial planes can’t go any which way, air traffic control routes planes around the US on “highways in the sky”).

A typical problem, then, is to route multiple robots around a fixed set of paths on a factory floor so that they all get place to place without running into each other.  To a mathematician, this is a problem about moving around on a graph.  Each vertex is a destination, and each edge from one vertex to another is a path from one place to another.  So it might look like this (the numbers on each edge is the length of that edge):

We can then think of robots in this picture as little disks moving along these paths. Of course, the whole problem is that you don’t want the robots running in to each other. This means each robot’s disk should bigger or smaller as needed to represent the size of the robot.  A graph with distances is called a metric graph and moving robots of various sizes around on such a graph is sometimes called “Pebble Motion on Graphs Problems”.

Actually developing a routing algorithm for moving the robots around is a very challenging problem. It is already interesting and difficult to understand which routings are even possible.

How do we tackle such a problem?  Mathematicians (like Drs. Dover and Özaydın) do something bold which actually simplifies the problem (once you get your mind around it).  They consider the set of all possible configurations of robot positions on the graph.

On the one hand, this a a much bigger and more complicated gadget, but on the other hand it is topological space called a configuration space.  This means you can unleash all the tools we have from topology to study the possible configurations of robots.

For example, a path in the configuration space translates into the simultaneous motion of the robots around the graph.  So knowing that there is a path between any two configurations in the configuration space tells you that it is possible to move the robots into any positions you like.

The first question, then, is how many different configuration spaces are there for a fixed graph if you vary the size of the robots.  To go back to our example of the factory, if you you replace your robots with new and improved models which are half the size of the old ones, does your old software still work, or are their new paths and configurations possible?  For example, if you have a single track of length 1 meter:

If you have a two gigantic robots which are each 3/4 meter across, then they can’t both fit on this track.  So there is zero possible configuration spaces for two big robots on this graph.  But if you replace them with two small robots (say of size 1 cm), then they now both fit on the graph and so you have at least one space of possible configurations.

As a topological space, you count spaces the same if they are homeomorphic.  So the first problem to ask (and which Drs. Dover and Özaydın answer) is how many non-homeomorphic configuration spaces are there?

You might think that there is infinitely many.  Or at least many, many, many.  In his 2011 PhD thesis at the University of Durham, Ken Deeley proved* that if you consider the first interesting case of two robots (one robot is easy!), then the number of possible configurations is actually finite.

Dr. Deeley gave an upper bound which is an exponential function in the number of edges on the graph.  The good news is that it only depends on the number of edges, not how they are connected or how long they are or anything else.  The bad news — as we all know — is that exponential functions get very big very fast.  So if it really is an exponential number of configuration spaces, then it is surely impractical to handle them on a case by case base.

Drs. Dover and Özaydın took on the challenge.  They prove the following amazing result:

Theorem:  If you have n robots traveling around a graph, then the number of possible configuration spaces is bounded by a polynomial of degree n in the number of edges in the graph.

For example, in Deeley’s case of two robots, the bound is a quadratic polynomial!  In fact, they even compute the bound for two robots on a graph with E edges in their paper and get that the number of configuration spaces is no more than:

That’s a heck of a lot less than an exponential bound!

A couple of notes before we go:

• They give an example with two robots where the number of configurations is bounded below by a quadratic polynomial.  This shows that you can’t get it down to a linear function.

• They also consider the case when the robots have various sizes.  In fact, they even allow you to set how close each pair of robots can get to each other.  Let’s say robots A, B, and C are all small, but A is carrying radioactive material.  If robot B is  sensitive and robot C is not sensitive to radioactivity, you can set the distance between A and B to be larger than the distance between A and C and B and C.  Their theorem still applies!

Very nice result!

“Imagine if all these fish were mathematical theorems…” — James Dover

* To be 100% mathematically honest, Deeley considered spaces up to homotopy, not homeomorphism.  There are fewer homotopy types, so a bound on homotopy types is not quite as strong a result as on homeomorphism types.  That is, Drs. Dover and Özaydın result implies Dr. Deeley’s but not vice versa.