Combinatorics

Faculty members involved

Rob Craigen (link) studies orthogonal matrices and related objects in the field of Combinatorial Matrix Theory. Combinatorial Matrix Theory is primarily concerned with the interesting combinatorial properties that arise as a result of restricting the entries of a matrix in some way -- usually to some finite set like {0,1}, or {0,1,-1} or some finite group (and performing algebra over its group ring). In this setting it is quite interesting to ask questions about orthogonal matrices and many surprising properties and elegant objects arise (not to mention useful -- across many areas of physics, information theory, electrical engineering, statistics, agriculture and computer science). Many of the objects of study are (or are related to) block designs, which are used in the design of experiments. And there arise numerous questions of elegance and depth, many of which have remained unsolved for over a century, though they are easy to state.

In 1893 the great mathematician Hadamard asked (and answered) a question about the determinant of matrices with complex number entries restricted to the unit disk. The answer required matrices whose rows were orthogonal and entries restricted to the unit circle. Offhand, Hadamard asked if one could further require the matrices to be real -- thus, have entries 1 or -1 --- from a purely analytic problem now arose this combinatorial curiosity, which we now call Hadamard matrices. Hadamard's conjecture is that these exist in all orders 4k; the conjecture remains unsolved today and is regarded as one of the great unsolved question of mathematics. Hadamard matrices, at first a curiosity, now find applications in quantum information theory, transform optics, discrete fourier transforms, error correction codes and many other areas. At the other end of design theory sits objects known as a projective plane. A similar open question about the orders in which these exist stands as another of the great unsolved problems in mathematics.

Between and beyond these two questions stands a panoply of tantalizing and deep open questions about the existence, structure and number of special matrices of innumerable types, now studied in this field.

Karen Gunderson (link) works in random graph theory. Random graphs are probability distributions on spaces of graphs and are studied to try to understand what sort of properties are typical or expected. The Erdos-Renyi random graphs are defined by takng a graph on some finite number of vertices with each possible edge included independently at random with some fixed probability. There are models of infinite random graphs like the family trees of Galton-Watson branching processes in which a random tree grows from a root with each vertex having a random number of child vertices independently according to a fixed distribution. Random graphs can also be defined by taking random subsets of a fixed (often large) graph.

Many properties of random graphs exhibit a threshold behaviour: very small changes in the value of some parameter lead to drastic changes in the likelihood of a graph having that property. Of interest is how processes on random graphs evolve over time. How does randomly scattered information spread in a graph? If some random subset of vertices are active and vertices become newly activated exactly when their number activated neighbours is above some threshold, are all vertices eventually activated? How does a graph change when new edges are added to reinforce local connections? These questions are related to percolation and bootstrap percolation processes.

Steve Kirkland (link) works in the areas of matrix theory and graph theory, with particular interest in the interplay between the two. His research in combinatorial matrix theory examines how key matrix properties, especially eigenvalue and eigenvector properties, are influenced by the zero-nonzero pattern of the entries of matrices in question. He also works in spectral graph theory, focusing on how spectral properties of various matrices associated with a graph (such as the Laplacian and signless Laplacian matrices) reflect structural properties of the graph such as connectivity and biparticity. He is also interested in the use of spectral graph theory in applied settings, including food webs, protein interaction networks, and quantum walks on graphs.

He also has an ongoing interest in entrywise nonnegative matrices and their applications, and has worked extensively on spectral properties of stochastic matrices. The latter are central to the analysis of discrete time, time homogeneous Markov chains on finite state spaces. His research in this direction includes results on stationary vectors and coefficients of ergodicity for stochastic matrices with specified directed graphs.

Representative recent publications

  • S. Kirkland and M. Neumann, Group Inverses of M-matrices and their Applications, CRC Press, 2013.
  • C. Godsil, S. Kirkland, S. Severini and J. Smith, Number-theoretic nature of communication in quantum spin systems, Physical Review Letters 109 (2012), 050502.
  • S. Kirkland, Sign patterns of eigenmatrices of nonnegative matrices, Linear and Multilinear Algebra 59 (2011), 999-1018.

News

MathCamp 2017 information is online.

Manitoba Workshop on Mathematical Imaging Science Friday, May 5, all day, Robert Schultz Lecture Theatre, details.

In an effort to help students, the Math department has put together the LevelUp program. See details here. Video explaining registration process is here.

Events

Thursday, May 4th, 2017 at 15:30, 418 Machray Hall
Tommy Kucera
Fibonacci and The Liber Abaci
(Seminar series : Colloquium)

Friday, May 12th, 2017 at 15:30, 418 Machray Hall
John Dallon
Modeling Amoeboidal Cell Motion -- Force vs Speed
(Seminar series : Colloquium)

Friday, August 4th, 2017 at 15:30, 418 Machray Hall
Jose Aguayo
TBA
(Seminar series : Colloquium)