Presenter: Leslie Hogben, Iowa State University, American Institute for Mathematics
http://www.public.iastate.edu/~lhogben/homepage.html
Given a graph, finding the associated matrix of minimum rank is generally an open problem. Professor Hogben introduced her work on the problem in her lecture; an abstract is provided below:
A graph G = (V,E) is a set of vertices V = {1, ..., n} and set of edges E of two element set of vertices. Given an n × n real symmetric matrix, one can create a corresponding graph of n vertices by putting an edge between vertices i and j whenever a given entry aij has a non-zero value. This graph will actually describe the family of all such n × n matrices with non-zero off-diagonal entries in the same positions. For any graph G, it is possible to find a matrix A described by G having rank n. However, finding a matrix with lower rank is more interesting. The complete graph on n vertices, Kn, has an edge between every pair of distinct vertices, so if A is described by Kn, then all off-diagonal entries are nonzero. There is such a matrix A that has rank 1. In contrast, the path on n vertices, which describes a tridiagonal matrix, requires rank at least n - 1. The minimum rank problem for graphs asks us to determine for any graph G the minimum of the ranks of matrices described by G and has applications to communication complexity problems. This talk will describe techniques that can be used to solve the minimum rank for some graphs; the general problem remains open.
After the lecture, Professor Hogben sat down with students in Math 300 (Dialogues in Mathematics) to answer their questions about life as a mathematician. Professor Hogben also shed some light on the graduate school admissions process. She encouraged students to find out about the climate of a particular department by visiting the university and talking to graduate students without faculty present.
With one last plug for Iowa State's summer REU program, Professor Hogben ended her conversation with the Math 300 class. For those of you who are interested, applications are due March 1, 2009 and can be found here: http://orion.math.iastate.edu/reu/.
----
Next week, Tuesday, February 3, the Math Department's lunch lecture series presents Megan Kerr from Wellesley College who will give a talk on Exploring (different) constant curvature spaces.
As always, lunch will be provided. We hope to see you in the Forum!