05C50 Online

05C50 Online is a biweekly virtual seminar about graphs and matrices held on a Friday, 10AM Central Time via Zoom. This is organized by Stephen Kirkland and Hermie Monterde from the University of Manitoba. Kindly fill out this subscription form to subscribe to our mailing list (and receive zoom links for upcoming talks).

Jan 17, 10am CT

Speaker: Sebastian Cioaba

Affiliation: University of Delaware (USA)

Title: Clique complexes of strongly regular graphs and their eigenvalues  

Abstract: It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). We investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this paper, we study the clique complexes of strongly regular graphs and determine the spectra of the triangle complexes of Hamming graphs, Triangular graphs and several other strongly regular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. This is joint work with Krystal Guo, Chunxu Ji and Mutasim Mim.

Preprint  |  Recording passcode: amdyN3+@ |  Slides

Jan 31, 10am CT

Speaker: Polona Oblak

Affiliation: University of Ljubljana (Slovenia)

Title: From multiplicity matrices to graphs with only two distinct eigenvalues

Abstract: The spectral properties of matrices with prescribed patterns have received significant attention in recent research. This talk examines symmetric matrices that share the off-diagonal zero-nonzero pattern with the adjacency matrix of a given graph, focusing on the spectra these matrices can achieve. This problem is widely recognized as the Inverse Eigenvalue Problem for a Graph. 

For a simple (not necessarily connected) graph, we introduce the concept of a multiplicity matrix, where each column represents an ordered multiplicity list of eigenvalues realized by a matrix corresponding to its connected component. We present the combinatorial notion of compatibility of two multiplicity matrices and show that their existence guarantees the existence of an orthogonal symmetric matrix corresponding to the join of two graphs. In some cases, this necessary condition is also sufficient, and we present several families of joins of graphs that are realizable by a matrix with only two distinct eigenvalues.

This talk is based on the joint work with Rupert H. Levene and Helena Šmigoc.

Preprint  |  Recording passcode: UyqSr66+ |  Slides

Feb 14, 10am CT

Speaker: Himanshu Gupta

Affiliation: University of Regina (Canada)

Title: Minimum number of distinct eigenvalues of Johnson and Hamming graphs

Abstract: This talk focuses on the inverse eigenvalue problems for graphs (IEPG), which investigates the possible spectra of real symmetric matrices associated with a graph G. These matrices have off-diagonal non-zero entries corresponding to the edges of G, while diagonal entries are unrestricted. A key parameter in IEPG is q(G), the minimum number of distinct eigenvalues among such matrices. We present lower bounds on q(G) based on the existence or non-existence of certain cycles in G. Notably, we show that every Johnson graph admits a {-1,0,1}-matrix with exactly two distinct eigenvalues. Additionally, we explore q(G) for Hamming graphs and other distance-regular graphs. This work is in collaboration with Shaun Fallat, Allen Herman, and Johnna Parenteau.

Preprint  |  Recording passcode: 5Jd7f8i^ |  Slides

Feb 28, 10am CT

Speaker: Krystal Guo

Affiliation: University of Amsterdam, QuSoft (Netherlands)

Title: Combinatorial constructions for quantum wires

Abstract: Perfect state transfer was proposed as type of "quantum wire"; as a part of a quantum algorithm, one may want to transfer a state from one qubit to another qubit. While this could be done using a series of swap gates, such an operation might be prone to noise. This motivated the idea that one could construct a time-evolution process that would perform the state transfer. Since its introduction in 2003, state transfer has been studied extensively with tools from algebraic graph theory and has let to many interesting combinatorial problems. 

In this talk, we introduce peak state transfer—a generalization of perfect state transfer in two-reflection discrete-time quantum walks—which quantifies the maximum state transfer achievable under unitary evolution even when perfect state transfer is out of reach. Using a spectral characterization, we can determine this completely for some families of graphs, including an infinite family where the amount of peak state transfer tends to 1 as the number of vertices grows. We will highlight the combinatorial connections and matrix techniques used.  

This is based on joint work with Vincent Schmeits. No knowledge of quantum computing will be assumed, but we will (attempt to) demonstrate running a program on the IBM quantum computer. 

This talk will be recorded. You may email the speaker for their slides.

Preprint  |  Recording passcode: ^7QvK7LX |  No slides

Mar 14, 10am CT

Speaker: Louis Deaett

Affiliation: Quinnipiac University (USA)

Title: Matroids and the minimum rank of zero-nonzero matrix patterns

Abstract: The zero-nonzero pattern of a matrix specifies precisely which of its entries are zero and which are nonzero.  We seek to understand what this information alone can tell us about the rank of the matrix.  In particular, the minimum rank of a zero-nonzero pattern is the smallest rank of a matrix with that pattern (which may depend on the field from which the matrix entries are chosen).  In this talk, we show how matroid theory can be applied to better understand this minimum rank.  We introduce a generalization of the problem to the setting of matroids; restricting this problem to the matroids representable over a fixed (infinite) field recovers the original problem over that field.  We also report on more recent work, and outline some new directions for applying matroid theory to better understand the minimum rank of zero-nonzero matrix patterns.

This talk will NOT be recorded. You may email the speaker for their slides.

Preprint  |  No recording  |  No slides

Mar 28, 10am CT

Speaker: Vilmar Trevisan

Affiliation: UFRGS - Universidade Federal do Rio Grande do Sul (Brazil)

Title: Eigenvalue location and applications

Abstract: We address the problem of estimating graph eigenvalues in terms of eigenvalue location, by which we mean determining the number of eigenvalues of a symmetric matrix that lie in any given real interval. Our focus is on a simple linear-time algorithm that works for symmetric matrices whose underlying graph is a tree. The algorithm has applications that go beyond estimating eigenvalues of a particular graph, and allow us to obtain properties of an entire class. We illustrate this with applications to relevant topics in Spectral Graph Theory. Such applications include contributions to the Inverse Eigenvalue Problem for Graphs, the Hoffman Program and the Brualdi-Solheid Problem.

This talk will be recorded and the speaker's slides will be shared on this website.

Preprint  |  Recording passcode:  |  Slides

Apr 11, 10am CT

Speaker: Paul Terwilliger

Affiliation: University of Wisconsin-Madison (USA)

Title: The subconstituent algebra of a graph,  the Q-polynomial property, and tridiagonal pairs of linear transformations

Abstract: This talk has two parts. In Part I, we review the subconstituent algebra T of a graph. We will discuss the Q-polynomial assumption, under which T is well behaved. Motivated by the first part, in Part II we discuss a linear-algebraic object called a tridiagonal pair. A tridiagonal pair consists of two diagonalizable linear transformations on a nonzero finite-dimensional vector space, that each act in a (block)-tridiagonal fashion on the eigenspaces of the other one. We will discuss the classification of tridiagonal pairs, and describe in detail a special case called a Leonard pair.

This talk will be recorded and the speaker's slides will be shared on this website.

Preprint  |  Recording passcode:  |  Slides

Apr 25, 10am CT

Speaker: Sarah Plosker

Affiliation: Brandon University (Canada)

Title: s-pair state transfer: 05C50 in disguise

Abstract: An s-pair state in a graph G is a quantum state of the form e_a+se_b, where a and b are vertices in the graph, s is a non-zero complex number, and e_a is simply a vector of appropriate length with 1 in the a-th position and zeros elsewhere (and similarly for e_b). Let M be the adjacency matrix, Laplacian matrix, or signless Laplacian matrix of G and define the transition matrix  U(t) =exp(-itM). Given two states 

u = e_a + re_b     and     μ = e_α + se_β

we say  perfect s-pair state transfer occurs from u to  μ  if 

U(τ) u = η μ

for some time τ, where η is a unit complex number.  We investigate quantum state transfer between s-pair states, develop  the theory of perfect s-pair state transfer and characterize such transfer in certain families of graphs. Our results are obtained primarily through a careful analysis of the spectral properties of the matrix M. 

This is joint work with Bahman Ahmadi, Ada Chan, Sooyeong Kim, Stephen Kirkland, and Hermie Monterde.

This talk will be recorded and the speaker's slides will be shared on this website.

Preprint  |  Recording passcode:  |  Slides

For titles and abstracts of previous talks, and links to recordings, please visit here .

Please contact Hermie Monterde  if you have inquiries about the seminar.