This one goes out to everyone studying related rates problems this weekend for Dr. Kujawa’s and Dr. Martin’s Calc I classes:
Good Luck with Finals!
Reply
Category Archives: @OU
Part time job in PHSC!
If you didn’t know, 
Spring is their busy time of year (graduating seniors and award ceremonies and whatnot), and they are looking for people who interested in working part time.
Kay Weiss, the executive director, would like to hire several people who are available between now and the end of June. She tells us the work is flexible in both hours and dates and any help you can provide will be greatly appreciated!
If you’re interested, you should either contact Ms. Weiss at
Sooner Astronaut Haise to visit OU!
CAC Speakers Bureau is bringing Fred Haise to OU on April 17 at 7pm in the Molly Shi Boren Ballroom! Haise is an University of Oklahoma graduate with a distinguished 20-year NASA career, he is best known as the lunar module pilot during the 1970 Apollo 13 space mission. There will be a meet & greet/photo opportunity after the event!
Sooner Astronaut Haise
In this photo from Apollo 13 (the Movie) Haise is on the left.
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.
Math Club on Wednesday!
Dr. Paul wondering who stole all the books from his shelves..
Dr. Sean Paul, a professor at the University of Wisconsin, will be speaking in the Math Club this
Wednesday, April 3rd at 5 pm in PHSC 1105.
Fun Fact: Dr. Paul is a Sooner! He graduated from OU in 1996 and then went to Princeton for graduate school. If you’re thinking about going on to grad school, here is a great chance to ask him for “real world” advice about how he went from OU to Princeton.
Dr. Paul will be talking about “The Cayley GKZ Theory of Discriminants, Resultants, and Multidimensional Determinants”. Here’s the abstract:
When do two complex number polynomials have a common root? When does a given polynomial have a double root? What is the determinant of a two by two by two matrix (the third “two” is not a typo) ? What is the determinant of a sequence (i.e. complex) of matrices?
We will give answers and hints to some of these questions in the talk.
— Dr. Paul’s abstract
There will also be the canonical Free Pizza!
Evolving Triangles!
You’ve probably already seen it on the second floor of PHSC next to the elevators, but we thought we should mention that the February POM is also posted online http://www.math.ou.edu/potm/.
Evolved Triangles from dirtytriangles.com
Also, a big shoutout to the winner of the Dec-Jan POM. Adam LaDine was randomly selected out of the correct entries. Congratulations Adam!
Math Club with Adrienne Jablonski!
There will be the first Math Club of the semester on
Wednesday, February 6th at 5 pm in PHSC 1105.
As summer/graduation approaches, one’s thoughts turn to jobs. Adrienne Jablonski will alk about jobs, internships, how to write a cover letter and a resume. Don’t miss it!
Plus, there’ll be the usual Free Pizza!
Talk this Tuesday!
Dr. Deem
Dr. Michael Deem from Rice University will be giving a talk for the general public this Tuesday at OU. It will be
Tuesday Jan. 29. 7:00 PM George Lynn Cross Hall (GLCH) 123.
Even though he is a professor of Bioengineering, his talk is right in our wheelhouse:
Title: In Search of Fundamental Mathematical Laws of Biology
Abstract: I will describe my participation over the past few years in an effort to find fundamental mathematical laws in biology. I will discuss a theory for understanding the emergence of multi-scale, hierarchical structure in biology. I will describe how modular structure in proteins, genetics, and biological networks may arise and how it can be understood. I will show the implications of the theory for engineering design, and I will discuss additional examples of structure formation in ecological food networks, developmental pathways, physiology, and social networks. I will then turn to theories of the immune system and describe a theory of the immune response to vaccines. I will illustrate this theory by application to design of the annual influenza vaccine. I will use this theory to explain limitations in the vaccine for dengue fever and to suggest a transport-inspired amelioration of these limitations.
Who needs reality when you’ve got purity? (Click through for an explanation!)
(Sadly, there probably won’t be pizza.)
Spring Career Events at OU
As the spring semester starts up, you should already be thinking about what you’ll be doing after the semester. If you’re graduating, you’re looking for a career and if not, then you should be thinking about summer internships. In any case, Adrienne Jablonski in the OU College of Arts and Sciences is looking out for you.
You can make an appointment with her on iAdvise and she’ll help you find openings, get your resume and application in order, and get ready for interviews.
She wanted us to let you know about some career events which are already on the schedule:
- February 20, OU Spring Career Fair, OMU Ballroom, 12:30-4:00pm
- February 27, A&S Student Networking Reception with Employers, OMU Beaird Lounge, 4:30-6:00pm, Free Food, Invitation to come.
Check them out!
And be sure to visit the CAS Career Development website:
Because you don’t want this to be your summer job.
Math Day 2012 Wrap-up
We’re a little late, but we wanted to tell you what happened at Math Day this fall. Remember, Math Day is our annual event for High School students. This year was a blockbuster!
We had a record annihilating 310 students from 14 schools from all over the state! Everyone had a great time, and Dr. Morgan’s talk about the mathematics of soap bubbles was a big hit.
Of course it was only possible thanks to the many people who volunteered. An extra thanks goes to the undergrads who helped. Thanks go to:
Julia Traughber
Teresa Ratashak
Jesse Doan
Eric Leung
Here’s a few photos of the event.
During the Fun Session on Flexagons
During the individual exams.
During Dr. Morgan’s talk on the Math of Soap Bubbles
During the Sooner Math Bowl
