Mathematics Research Communities

MRC Week 3: June 14 – 20, 2020

Finding Needles in Haystacks: Approaches to Inverse Problems using Combinatorics and Linear Algebra


  • Shaun Fallat, University of Regina
  • H. Tracy Hall, NewVistas LLC
  • Leslie Hogben, Iowa State University and the American Institute of Mathematics
  • Bryan Shader, University of Wyoming
  • Michael Young, Iowa State University

Inverse eigenvalue problems encompass many important problems in science and engineering and often can be reduced to the mathematical question of whether or not there is a matrix with a prescribed structure whose invariants (eigenvalues) have a desired property. Progress has been slow because particular inverse eigenvalue problems can be difficult—much like finding a needle in a haystack. The inverse eigenvalue problem of a graph asks us to determine the possible eigenvalues of a real symmetric matrix with the nonzero off-diagonal pattern described by the edges of a graph. Recently developed tools have accelerated progress and opened up new lines of inquiry by giving linear algebraic and combinatorial criteria for the existence of a “nice” needle in a given haystack that guarantees the existence of a needle in each nearby haystack. The inverse eigenvalue problem of a graph has also stimulated work on zero forcing, a graph coloring process that has applications to graph searching, monitoring electric power networks, and control of quantum systems, in addition to serving as an upper bound for maximum eigenvalue multiplicity. Recent work on zero forcing has also included investigations of propagation time (the minimum time needed to color the entire graph starting with a set of minimum possible size, and throttling (minimizing the sum of the resources needed to and the time needed to accomplish a task). This MRC conference will provide participants with the expertise in needed to launch productive research projects in these new lines of inquiry. We expect that a participant will have expertise linear algebra or graph theory, but need not have worked in both. We look forward to bringing together advanced graduate students, postdocs, and junior faculty from a mix of backgrounds.

Applications are being accepted on until the deadline of 11:59 p.m. Eastern Time, February 15, 2020.

For questions about the application process, please  contact Kim Kuda at the AMS.