Packings and Realizations of Degree Sequences with Specified Substructures

Tyler Seacrest, UNL

Meeting Time: April 19, 2011, 2:00-2:50pm, Avery 347

Abstract: This talk is about relationships between degree sequences, balanced partitions, and packings. We will describe several results along these lines, particularly a degree sequence version of a conjecture of Bollobas and Scott regarding balanced partitions with two parts. This has application to packing edge-disjoint perfect matchings. We will then discuss a theorem regarding balanced partitions of the vertices of graphs, proven using the probabilistic method. This theorem roughly states that every graph has a balanced partition where each vertex has many neighbors in each part. This has many applications, including proving an approximate version of the Bollobas-Scott Conjecture and one we will discuss more in depth: packing Hamiltonian cycles.