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.