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!).
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.
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.
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!
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:
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.
Adrienne Jablonski let us know that PCI here in Norman is very keen on hiring some math students to be summer internships. The information is below, or you can contact Adrienne for further information. She can also help you get your resume, etc. in good shape.
The PCI College Internship Program is a structured, supervised, short- term opportunity for undergraduate and graduate students to perform tasks that build on classroom theories to make real decisions and gain relevant work experience. The typical internship at PCI lasts one semester, with Interns typically working up to 20 hours per week during the Fall or Spring semester and up to 40 hours per week during the Summer semester. Participating students are paid and may also receive academic credit from their university.
To be considered for the Internship Program at PCI, applicants must have completed a minimum of 90 credit hours with a grade point of 3.5 or above. Work will be performed at the PCI Corporate office at 301 David L. Boren Boulevard, Suite 2000, Norman, OK. There is a CART bus stop at the PCI Norman office as well as free parking.
Interested students may apply at – www.powercosts.com/pci-internshipsA few of our Summer projects include, but are not limited to:
- Business Analyst-Intern in Market Systems communicating with product owners, quality assurance and delivery teams to focus on developing a baseline regression test plan and test case suite for the quality assurance of an emerging product line.
- Technical Writer-Intern focusing on PCI’s Data Warehouse product combining information from multiple sources, including SME interviews and software analysis, to provide a description of data movement between software systems.
- Business Analyst-Intern in Market Systems working with PCI’s Deal Management team to produce documentation and other training material for different Deal Management software modules.
We told you in January about the fantastic TORUS math conference (note: the O in TORUS stands for Oklahoma!). Jeffery Dittenber, an OU math major who went with Dr. Hall to TORUS, volunteered to tell about his many adventures. We asked him the same questions we asked the ladies who went to Nebraska. It sounds like TORUS should also become an annual event for OU students!
Unfortunately, TORUS is not held in the Stanford Torus.
Here’s what Jeffery had to say about TORUS:
0. Why did you decide to go to TORUS?
I decided to go because I love math and learning about math in a no pressure atmosphere. I was interested in seeing what a math conference would be like. Also, I was interested in finding out about student presentation material for next semester.
1. What happens at this conference? What did you do there?
The conference has two key speakers, who were math professors (PhDs) and they were separated by several student presentations. The student presentations were very broad in subject matter and all understandable to a math major. There was a panel comprised of people who work in mathematics careers. They answered questions from the audience. There was lunch included and served as well as snacks and beverages. At the end, there was a friendly “Math Jeopardy” competition that was a lot of fun.
2. Give 5 words that describe the TORUS conference.
Fun. Friendly. Inspiring. Interesting. Worthwhile. Repeatable.
3. What was your expectation for the conference? What did it actually turn out to be like?
I thought I would hear talks on higher level geometries that were very specialized and I would just sort of listen and nod and try to make sense of what I was hearing. On the contrary, it was all very understandable, and I look very forward to presenting my own talk next year. I might do a talk on the Buckingham Pi Theorem. I just learned about it today from a colleague.
4. What was the coolest math thing you heard?
The coolest thing I heard was that there were engineers turning to mathematicians to find formulas and equations for their projects. I was very happy to hear this!
5. What’s the best piece of information you received at the conference? The thing you will be sure to remember?
The best piece of information I learned my way of learning and studying math (by making videos and tutoring) is a real and researched way to learn math. I thought I was the only person who had to be able to explain how to do a problem to be able to understand it. I learned a lot that vindicated a lot of ideas I had about learning and teaching math.
6. What would you say to someone thinking about going to next year’s conference?
I say definitely do it. Even present a talk. I think it is a great experience and probably a good “trial run” for doing mathematics professionally.
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!
We told you in November about freedom fighter Supap Kirtsaeng. He made a tidy profit reselling international edtions of textbooks on eBay. Since they are sold in his home country of Thailand for much cheaper than even the used price here in the US, he was able to make big bucks while saving students equally big bucks.
Not surprisingly, the publishers took umbrage and went after Kirtsaeng in the courts. Here things get muddled. On the one hand, the publishers said that by buying an international edition you were agreeing to their stated policy that the books wouldn’t be sold in the US. on the other hand, US law has a policy of “first sale”: once you buy something, it’s yours to do with as you like and the seller doesn’t have any say in it*.
It went all the way to the Supreme Court and they just announced their ruling. From Justice Breyer writes for the majority:
…we ask whether the “first sale” doctrine applies to protect a buyer or other lawful owner of a copy (of a copyrighted work) lawfully manufactured abroad. Can that buyer bring that copy into the United States (and sell it or give it away) without obtaining permission to do so from the copyright owner? Can, for example, someone who purchases, say at a used bookstore, a book printed abroad subsequently resell it without the copyright owner’s permission?
In our view, the answers to these questions are, yes.
– From the Supreme Court’s ruling
You can read further details in this article at arstechnica.com.
Hmmm, maybe I should look for an international edition for my next class!
* “But wait, what about computer software? Does this mean I can sell my Apple software?” Nope. Software (exactly to avoid the “first sale” rule) is not “sold”. You usually buy a license to use the software, but don’t actually own the software. Tricky software people!
