A packing problem and a potential packing problem


Meeting Time: Sept. 1, 2009, 2:00-2:50pm

Abstract: Packing problems are very common in math, in computer science, and on vacations! In graph theory, we say that two n vertex graphs G and H pack if they can be placed on the same n vertices without any edges overlapping. I will cover a proof of one of the first major results in this area due to Sauer and Spencer in 1978, which states that if twice the product of the maximum degrees of each graph is less than n, then the two graphs pack. I will then move on to a Kundu's k-factor theorem, which can be seen as a "potential" version of the packing problem.