The Oberwolfach Problem

My web browsing habits, especially my use of wikipedia, bears a striking similarity to the basic principles of Graph Theory: I begin with at a page—say, a list of mathematical concepts named after places—and eventually “command-click” my way down the blue hyperlink rabbit hole that ultimately and inevitably leads to an obscene number of tabs in my browser and hours of procrastination. Were I to plot a series click on a specific session, I would most likely use a directed graph. Each vertex would be a webpage and edges would point in the direction of which pages linked to which. This is one simple example of the many applications and analytical potential of graph theory.

So far, I have learned most of the introductory principles of Graph Theory by reading Hartsfield and Ringel’s Pearls in Graph Theory and doing the exercises that follow each section. Professor Schalekamp, my mentor, has been an invaluable resource and it was his suggestion that led me to the focus of my project: the Oberwolfach Problem. This problem (named after Oberwolfach, a city in Germany and the site of a mathematical institute), in graph theoretical terms, is:

Given a graph T with 2n+1 vertices that is regular of degree  2, decompose the complete graph K2n+1 into subgraphs isomorphic to (Hartsfield et al.).

Another way of describing the problem is as follows:

If a group of people meet ever so often to have dinner together, what is the minimum number of time they must meet for everyone to sit next to everyone else at least once given an odd number of people and any number of dinner tables seating every participant.

This problem has been solved for many specific cases (for example, if there are 3 people and 1 table then the problem is solved) but there is no general solution yet. I have decided to investigate a specific case of this and see if any patterns arise.

Comments

  1. michaeltesta says:

    I think this is a great topic. Graph theory is a valuable subset of mathematics, but unfortunately most people know little about it, including myself. I’m curious about why you decided to study the Oberwolfach Problem. Did you have a particular insight you thought would apply well to the problem? Anyway, I know you’ve been working hard on this, so keep up the good work. I’m looking forward to hearing about what you come up with, but I’ll need you to explain it in layman’s terms. I’m just a budding social scientist who would probably ask not how many times these people would need to meet to sit next to each person, but rather what compels these people to meet so many times.