Graduate Seminar

Patrick Bennett
Carnegie Mellon University
Title: Lajos Posa and the Hamiltonicity of Graphs

Abstract: A graph G = (V, E) is an ordered pair consisting of a finite set V whose elements are called "vertices", and another set E of "edges" (which are unordered pairs from V). We usually draw a graph by making a dot for each vertex and drawing a line segment between any two vertices that form an edge. A cycle in G is a sequence of vertices x_1, ... x_k such that all pairs of consecutive vertices in the list, as well as the pair (x_1, x_k) are all edges. A cycle is Hamiltonian if there is a cycle with k = |V| (i.e., a cycle that uses every vertex). G is called "Hamiltonian" if it has a Hamilton cycle.

Lajos Posa is a cool guy who hung out with Paul Erdos and who has a number of results relevant to the Hamiltonicity of graphs, including some results about the probability that a random graph is Hamiltonian. In this talk we'll learn about Posa and his work.

Date: Thursday, January 31, 2013
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Brian Kell