2022 Fall
1. SEPTEMBER 23, 10am CT
Speaker: RB Bapat
Affiliation: Indian Statistical Institute (India)
Title: Resistance matrix of a balanced directed graph
Abstract:
We first review some known results about resistance matrix of an undirected graph. We then define resistance distance in a strongly connected, directed graph. When the graph is balanced, that is, the indegree and the outdegree of any vertex are the same, we show that many properties of resistance matrix continue to hold. The definition of resistance distance uses the Moore-Penrose inverse of the Laplacian matrix of the graph. Some open problems are proposed. The talk is based on joint work with R. Balaji and Shivani Goel.
This talk was not recorded and slides are not shared on this website. However, the participants may email the speaker for their slides.
2. OCTOBER 7, 10am CT
Speaker: Pauline van den Driessche
Affiliation: University of Victoria (Canada)
Title: Some applications of sign pattern matrices
Abstract:
Biological systems often give rise to systems of first order ordinary differential equations (ODEs). Linearization then yields a system x'=Ax, where A is the community matrix. By contrast, mechanical systems often give rise to a second order ODE system x''=Ax'+Bx, which is equivalent to a first order system with coefficient matrix with block form
A B
I 0.
In cases for which the signs rather than the magnitudes of matrix entries are known, the matrices become sign patterns with entries { +, -, 0 }. What can be determined about the behaviour of a system governed by such sign pattern matrices? This general question is addressed by developing results on sign patterns and their associated digraphs. Some answers in special cases are given that determine stability and inertia properties important for the underlying systems.
This talk was not recorded and slides are not shared on this website. However, the participants may email the speaker for their slides.
3. OCTOBER 21, 10am CT
Speaker: Richard Brualdi
Affiliation: University of Wisconsin-Madison (USA)
Title: The Permutation/Alternating Sign Matrix Cones
Abstract:
After a review of n-by-n permutation matrices and n-by-n alternating sign matrices (ASMs), and their relationship, we will discuss the cones that they generate and their Hilbert Bases.
This talk was not recorded and slides are not shared on this website. However, the participants may email the speaker for their slides.
4. NOVEMBER 4, 10am CT
Speaker: Jane Breen
Affiliation: Ontario Tech University (Canada)
Title: Kemeny's constant for Markov chains and random walks on graphs
Abstract:
Kemeny's constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are. Though it was first introduced in the 1960s, interest in this concept has recently exploded.
This talk will provide an introduction to Markov chains, an overview of the history of Kemeny’s constant, discussion of some applications, and a survey of recent results, with an emphasis on those where the combinatorial structure of the Markov chain is of interest. This comes to the forefront when the Markov chain in question is a random walk on a graph, in which case Kemeny's constant is interpreted as a measure of how `well-connected' the graph is.
The slides for this talk are not shared on this website. However, the participants may email the speaker for their slides.
No preprint | Recording passcode: cAey+5PM | No Slides
5. NOVEMBER 18, 10am CT
Speaker: Gabriel Coutinho
Affiliation: Universidade Federal de Minas Gerais (Brazil)
Title: Open problems in quantum walks
Abstract:
In this talk I will talk about some of my favorite problems which remain open in the field of continuous-time quantum walks in graphs.
No preprint | Recording passcode: 49@eYfrp | Slides
6. DECEMBER 9, 10am CT
Speaker: Jephian Lin
Affiliation: National Sun Yat-sen University (Taiwan)
Title: Inverse eigenvalue problem for a graph
Abstract:
We often encounter matrices whose pattern (zero-nonzero, or sign) is known while the precise value of each entry is not clear. Thus, a natural question is what we can say about the spectral property of matrices of a given pattern. When the matrix is real and symmetric, one may use a simple graph to describe its off-diagonal nonzero support. For example, it is known that an irreducible tridiagonal matrix (whose pattern is described by a path) only allows eigenvalues of multiplicity one. In contrast, a periodic Jacobi matrix (whose pattern is described by a cycle) allows multiplicity two but no more. The inverse eigenvalue problem of a graph (IEPG) focuses on the matrices whose pattern is described by a given graph and studies their possible spectra. In this talk, we will go through some of the histories of the IEPG and see how combinatorial methods (zero forcing) and analytic methods (implicit function theorem) can come into play in modern-day research.
2023 Winter
7. JANUARY 13, 10am Central Time
Speaker: Mike Tait
Affiliation: Villanova University (US)
Title: Proving algebraic results using only graph theory and linear algebra
Abstract:
We discuss how to use spectral graph theory to count subgraphs of graphs where the subgraph counted is motivated by finite field versions of questions in geometric measure theory. One representative question is the following:
Let E be a set in F_q^d, and \alpha and \beta be elements in F_q^*. How large does E need to be to guarantee that there are four points w, x, y, and z in E such that they form a rectangle of side lengths \alpha and \beta, i.e.
( w - x ) \cdot ( x - y ) = 0
( x - y ) \cdot ( y - z ) = 0
( y - z ) \cdot ( z - w ) = 0
( z - w ) \cdot ( w - x ) = 0
and
|| w - x || = || y - z || = \alpha and || x - y || = || z - w || = \beta.
We provide a general framework which answers this and other similar questions as a corollary. This is joint work with Thang Pham, Steven Senger, and Vu Thi Huong Thu.
Preprint | Recording passcode: $Lf8GW99 | Slides
8. JANUARY 27, 10am Central Time
Speaker: Helena Šmigoc
Affiliation: University College Dublin (Ireland)
Title: Spectral arbitrariness for trees fails spectacularly
Abstract:
The Inverse Eigenvalue Problem for a Graph (IEPG) asks for all possible spectra of real symmetric matrices whose pattern of off-diagonal nonzero entries is specified by a given graph. A subproblem to the IEPG is to determine all possible ordered multiplicity lists of eigenvalues. Once an ordered multiplicity list m is known to be realisable for a graph G, one needs to determine the set of all possible assignments of eigenvalues for m. If every set of distinct eigenvalues can be assigned to m, then we say that m is spectrally arbitrary for G. We present an infinite family of trees and ordered multiplicity lists whose sets of realising eigenvalues are highly constrained. Furthermore, we exhibit examples where multiplicity lists can only be achieved by a unique (up to shifting and scaling) set of eigenvalues.
This talk is based on joint work with Shaun M. Fallat, H. Tracy Hall, Rupert H. Levene, Seth A. Meyer, Shahla Nasserasr and Polona Oblak.
The slides for this talk are not shared on this website. However, the participants may email the speaker for their slides.
Preprint | Recording passcode: i$47j$^t | No slides
9. FEBRUARY 10, 10am Central Time
Speaker: Mahsa N. Shirazi
Affiliation: University of Manitoba (Canada)
Title: On weakly Hadamard diagonalizable graphs
Abstract:
An interesting question in spectral graph theory is about the structure of the eigenvectors of matrices associated with graphs. A graph is weakly Hadamard diagonalizable (WHD) if its Laplacian matrix L can be diagonalized with a weakly Hadamard matrix. In other words, if L = PDP^{-1} , where D is a diagonal matrix and P has the property that all entries in P are from {0,-1,1} and that P^TP is a tridiagonal matrix. In this talk, I will present some necessary and sufficient conditions for a graph to be WHD. Some families of graphs which are WHD will also be presented.
This work is part of a research project done with the discrete math research group (DMRG) at the University of Regina
Preprint | Recording passcode: $rB8!V4D | Slides
10. FEBRUARY 24, 10am Central Time
Speaker: Irene Sciriha
Affiliation: University of Malta (Malta)
Title: Walks Reveal Important Graph Substructures
Abstract:
Non--isomorphic graphs with isomorphic canonical double cover (CDC) have the same number of walks of arbitrary length from corresponding vertices of the same degree. The total number of walks, for a specific length, depends only on the main eigensystem. What combinatorial properties do graphs with the same eigenspace have in common? A hierarchy of properties of classes of graphs is established in view of their CDCs, walk matrices, main eigenvalues, eigenvectors and eigenspaces. The main eigenspace of the adjacency matrix of a graph turns out to be the image of the walk matrix. This leads to a fixed parameter tractable algorithm that decides whether a graph is Hamiltonian, a problem that is NP hard and NP complete in general.
Preprint | Recording passcode: SzK5DA#% | Slides
11. MARCH 10, 10am Central Time
Speaker: Rajesh Kannan
Affiliation: Indian Institute of Technology Hyderabad (India)
Title: On the Eccentricity Matrices of Trees: Invertibility, Inertia and Spectral Symmetry
Abstract:
The eccentricity matrix ε(G) of a connected graph G is obtained from the distance matrix of G by keeping the largest nonzero entries in each row and each column and leaving zeros in the remaining ones. The eigenvalues of ε(G) are the ε-eigenvalues of G. It is well-known that the distance matrices of trees are invertible, and the determinant of such a matrix depends only on the number of vertices of the tree. We show that the eccentricity matrix of tree T is invertible if and only if either T is star or P_4. Also, we show that any tree with odd diameter has 4 distinct ε-eigenvalues, and any tree with even diameter has the same number of positive and negative ε-eigenvalues (which is equal to the number of ’diametrically distinguished’ vertices). Finally, we will discuss trees with ε-eigenvalues that are symmetric with respect to the origin. This is joint work with Iswar Mahato.
Preprint | Recording passcode: J.c8?2az | Slides
12. MARCH 24, 10am Central Time
Speaker: Christino Tamon
Affiliation: Clarkson University (USA)
Title: Can quantum transport occur on infinite graphs?
Abstract:
Suppose Alice can send a quantum message to Bob in a quantum system modeled as a finite graph. But, imagine there is an eavesdropper which can attach an infinite-dimensional quantum system to the finite graph used by Alice and Bob. Can Alice still send quantum messages to Bob in the presence of this powerful external probe? We explore this question in this talk.
This is a joint work with Pierre-Antoine Bernard, Luc Vinet, and Weichen Xie.
Preprint | Recording passcode: Ghr&$20Q | Slides
13. APRIL 7, 10am Central Time
Speaker: Gary R.W. Greaves
Affiliation: Nanyang Technological University (Singapore)
Title: Graphs with three eigenvalues
Abstract:
Graphs having three distinct eigenvalues are a fundamental object of study in spectral graph theory. Strongly regular graphs are the most well-studied examples. In 1995, at the 15th British Combinatorial Conference, Willem Haemers asked do there exist any connected graphs having three distinct eigenvalues apart from strongly regular graphs and complete bipartite graphs. Haemers’ question prompted responses from Muzychuk-Klin and Van Dam who found new families of nonregular graphs having three distinct eigenvalues.
Muzychuk and Klin initiated the study of a graph with three distinct eigenvalues via its Weisfeiler-Leman closure. They classified such graphs whose Weisfeiler-Leman closure has rank at most 7. In this talk, I will give an overview of the history of non-regular graphs having three distinct eigenvalues. I will present our recent results about such graphs whose Weisfieler-Leman closure has small rank. Our results include a correction of the literature (where the rank 8 case was erroneously claimed to be impossible) and a discussion of further study.
This talk is based on joint work with Jose Yip.
The slides for this talk are not shared on this website. However, the participants may email the speaker for their slides.
No preprint | Recording passcode: 1efy5A#0 | No slides
14. APRIL 21, 10am Central Time
Speaker: Nair Abreu and Claudia Justel
Affiliation: Universidade Federal de Rio de Janeiro (Brazil) and Instituto Militar de Engenharia (Brazil)
Title: What do the Laplacian eigenvalues say about the structure of a graph?
Abstract:
In this talk, our objective is to convince you that, in recent years, the eigenvectors and eigenvalues of matrices associated with graphs are one of the most important topics to be learned in Applied Linear and Computational Mathematics. We will try to do this only through the Laplacian matrices and their respective integer eigenvalues.
No preprint | Recording passcode: ^6jT2Jc6 | Slides
15. MAY 5, 10am Central Time
Speaker: Aida Abiad
Affiliation: Eindhoven University of Technology (Netherlands), Ghent University and Vrije Universiteit Brussel (Belgium)
Title: Eigenvalue bounds for the independence and chromatic number of graph powers
Abstract:
In this talk I will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixed-integer linear programming in order to optimize such bounds. Some infinite families of graphs for which the new bounds are tight will also be shown.
Preprint | Not recorded | Slides
16. MAY 19, 10am Central Time
Speaker: Sukanta Pati
Affiliation: Indian Institute of Technology Guwahati (India)
Title: Some observations on algebraic connectivity of graphs
Abstract:
Let G be a connected simple graph and L be its Laplacian matrix. Let v be a cut vertex and B be a branch at v. Assume that v_1 is the only vertex in B adjacent to v. Let P be a path that starts at v_1 and stays inside B. It is shown that the algebraic connectivity decreases if we do an appropriate sliding operation along the path. Similar results for trees were known decades ago. The techniques involve the notions of Perron branches and bottleneck matrices developed by Kirkland, Neumann, Shader and others.
2023 Fall
17. September 8, 10am CT
Speaker: Bryan L. Shader
Affiliation: University of Wyoming (USA)
Title: Temptations on Tournaments
Abstract:
Mathematically, a tournament is an orientation of a complete graph. In layman terms, a tournament records the results of a competition with n players, where each game pits two players against each other, each pair of players compete against each other exactly once, and there are no ties. Historically, tournaments (orientations of complete graphs) have been a rich source of interesting mathematical problems that have in turn catalyzed new or improved mathematical techniques. I, like many others, am frequently lured by problems related to tournaments. This talk will discuss some tempting linear algebraic and combinatorial problems related to adjacency matrices of tournaments, skew-adjacency matrices of tournaments, two-person tournament games.
Preprint | Recording passcode: @9JH=1=j | Slides
18. September 22, 10am CT
Speaker: Sasmita Barik
Affiliation: Indian Institute of Technology Bhubaneswar (India)
Title: Graphs with the reciprocal eigenvalue property
Abstract:
Let G be a simple connected graph and A(G) be its adjacency matrix. A nonsingular graph G is said to have the reciprocal eigenvalue property if the reciprocal of each eigenvalue of G is also an eigenvalue. Furthermore, if each eigenvalue of G and its reciprocal have the same multiplicity, then G is said to have the strong reciprocal eigenvalue property. Such graphs exist and have been studied in the past. A general question remained open. Can there be a graph that has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? We first prove that there is no such nontrivial tree. Suppose that G is singular and the characteristic polynomial of G is x^{n-k} ( x^k + a_1x^{k-1} + ... + a_k ). Assume that A(G) has rank k, so that a_k\neq 0. Can we ever have |a_k|=1? The answer turns out to be negative. As an application, we prove that there is no nontrivial singular graph whose nonzero eigenvalues satisfy the reciprocal eigenvalue property. This talk is based on joint work with Debabrota Mondal, Sukanta Pati, and Kuldeep Sarma.
Preprint | Recording passcode: !o@6Tdeb | Slides
19. October 6, 10am CT
Speaker: Thomás Jung Spier
Affiliation: Federal University of Minas Gerais (Brazil)
Title: No perfect state transfer in trees with more than 3 vertices
Abstract:
The adjacency matrix A of a graph G is the Hamiltonian for a continuous-time quantum walk on the vertices of G. If u and v are distinct vertices in G, we say perfect state transfer from u to v occurs if there is a time t such that the (u,v)-entry of exp(iAt) has absolute value 1. In this talk, we show that the only trees that admit perfect state transfer are P_2 and P_3. This is joint work with Gabriel Coutinho and Emanuel Juliano.
Preprint | Recording passcode: h8r=#B0D | Slides
20. October 20, 8am CT
Speaker: Hajime Tanaka
Affiliation: Tohoku University (Japan)
Title: On certain extremal configurations in Q-polynomial distance-regular graphs
Abstract:
In this talk, I will discuss certain extremal configurations in Q-polynomial distance-regular graphs (or P- and Q-polynomial association schemes), which we call descendents. The descendents of a hypercube are precisely its faces. I will show how they arise naturally and play a role in various topics, such as the Erdős-Ko-Rado theorems, the Assmus-Mattson theorems, orthogonal (Laurent) polynomials, and Ambainis' quantum algorithm for the element distinctness problem (if time allows). As algebraic tools, I will mention two matrix algebras, the (commutative) Bose-Mesner algebra and the (noncommutative) Terwilliger algebra.
No preprint | Recording passcode: Y*+!4t*E | Slides
21. November 3, 10am CT
Speaker: Hermie Monterde
Affiliation: University of Manitoba (Canada)
Title: Bridging continuous quantum walks and spectral graph theory
Abstract:
Let G be a graph with adjacency or Laplacian matrix M. The continuous quantum walk on G is determined by the complex unitary matrix U(t)=exp(itM), where i^2=-1 and t is a real number. Here, G represents a quantum spin network, and its vertices and edges represent the particles and their interactions in the network. The propagation of quantum states in the quantum system determined by G is then governed by the matrix U(t). Quantum walks are of great interest in quantum computing because not only do they produce algorithms that outperform classical counterparts, but they are also promising tools in the construction of operational quantum computers. In this talk, we give an overview of continuous quantum walks, and discuss old and new results in this area with emphasis on the concepts and techniques borrowed from spectral graph theory.
No preprint | Recording passcode: U042yY3. | Slides
23. November 17, 10am CT
Speaker: Beatrice Meini
Affiliation: University of Pisa (Italy)
Title: An edge centrality score based on the Kemeny constant
Abstract:
Given a connected undirected graph G = (V,E), where V is the set of vertices and E the set of edges (possibly with weights), denote by A the associated adjacency matrix. The Kemeny constant of the graph G is defined as the Kemeny constant of the Markov chain with transition matrix P, where P is obtained by scaling the rows of A to obtain a stochastic matrix.
The Kemeny constant gives a global measure of the non-connectivity of a network . Indeed, if G is not connected then the Kemeny constant cannot be defined or, in different words, it takes the value infinity. We introduce and analyze a definition of edge centrality, based on the variation of the Kemeny constant.
More precisely, we may formally define the Kemeny-based centrality score of an adge as the change of the connectivity of the graph measured by the Kemeny constant, when such edge is removed from the graph itself. A drawback of this definition of centrality score is that there exist graphs where the score is negative for some edge. In the literature, this fact is known as the Braess paradox. To overcome this drawback we propose a modified centrality measure, which is nonnegative for any graph and for any edge. The underlying idea consists in replacing an edge with a loop at each vertex. By applying a corollary of the Courant-Fischer theorem we prove that the score is always nonnegative.
This definition cannot be applied in the case of a cut-edge. This drawback is solved by introducing the concept of regularized centrality score, depending on a regularization parameter. It is interesting to point out that the regularized approach can be applied also to graphs that are not connected.
We have designed effective algorithms implementing the computation of the score of a single edge, or of all the edges of a graph. Our algorithms have been tested both on synthetic graphs and on graphs representing real road networks, in particular, we have considered the maps of Pisa and of the entire Tuscany. From our numerical experiments, it turned out that this measure is robust, effective, and realistic from the model point of view. Indeed, our model succeeds in detecting bridges on the river Arno and overpasses over the railroad line as important roads in the Pisa road map. Moreover, the computation is sufficiently fast even for large road networks.
More details can be found in the paper D.Altafini, D.A. Bini, V. Cutini, B. Meini, and F. Poloni.
Preprint | Recording passcode: ?!%@4&Ea | Slides
24. December 8, 10am CT
Speaker: Michael Young
Affiliation: Carnegie Mellon University (USA)
Title: The relationship between zero forcing and vertex covers
Abstract:
Zero forcing is a type of graph propagation based on the color-change rule: Given graph $G$, if each vertex of $G$ is colored either white or blue, and vertex $v$ is a blue vertex with only one white neighbor $w$, then change the color of $w$ to blue. In this talk we prove a conjecture formulated by the automated conjecturing program called \emph{TxGraffiti}. The conjecture states that in a claw-free graph, the vertex cover number of the graph is at least the zero forcing number of the graph. We also prove a relationships about the zero forcing and independence number of a connected subcubic graph.
This talk is not recorded, but you may email the speaker for their slides.
2024 Winter
25. January 12, 10am CT
Speaker: Leslie Hogben
Affiliation: Iowa State University and American Institute of Mathematics (USA)
Title: Uniform and apportionable matrices
Abstract:
There has been extensive study of diagonalization of matrices, or finding the Jordan Canonical Form for a matrix that is not diagonalizable. Diagonalization can be viewed as using a similarity to concentrate the magnitude of all the entries with a small subset of entries. Here we study what can be viewed as reversing this process, spreading out the magnitudes as uniformly as possible. A uniform matrix plays the role of a diagonal matrix in this process. A square complex matrix is uniform if all entries have the same absolute value and a square complex matrix is apportionable if it is similar to a uniform matrix; the problem of apportioning by unitary similarity is also studied. Hadamard matrices and discrete Fourier transforms are important examples of uniform matrices. Matrix apportionment has connections to classical problems of combinatorics, including graceful labeling of graphs, and connections with the new study of instantaneous uniform mixing in quantum walks.
Various results and examples are presented. Every rank one matrix is unitarily apportionable and there is a procedure to find a unitary apportioning matrix. A necessary condition for a matrix to be apportioned by a unitary matrix is established and this condition is used to construct a set of matrices with nonzero Lebesgue measure that are not apportionable by a unitary matrix. There are examples of matrices A such that there are infinitely many possible magnitudes of entries of the uniform matrices MAM^{−1} and examples of spectra that are not attainable by any uniform matrix.
Joint work with A. Clark, B. Curtis, and E.K. Gnang.
Preprint | No recording | No slides
26. January 26, 10am CT
Speaker: Enide Andrade
Affiliation: University of Aveiro (Portugal)
Title: New results on graph partitions and Fiedler theory
Abstract:
In this seminar we recall the spectral partitioning method based on a Fiedler vector, i.e., an eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix of a graph. This problem corresponds to the minimization of a quadratic form associated with this matrix, under a certain constraint. We introduce a similar problem using the $\ell_1$-norm to measure distances and compare the optimal solutions for both problems.
Preprint | Recording passcode: E7%Lt%L5 | Slides
27. February 9, 10am CT
Speaker: Hiranmoy Pal
Affiliation: National Institute of Technology Rourkela (India)
Title: A Characterization of State Transfer on Double Subdivided Stars
Abstract:
We study the existence of quantum state transfer on double subdivided star, which is obtained by joining the coalescence vertices of a pair of subdivided stars. Using the Galois group of the characteristic polynomial of a double subdivided star, we analyze the linear independence of its eigenvalues which uncovers no perfect state transfer in double subdivided stars when considering the adjacency matrix as the Hamiltonian of corresponding quantum system. We finally establish a characterization on double subdivided stars exhibiting pretty good state transfer.
Preprint | Recording passcode: Xbek6+K? | Slides
28. February 23, 10am CT
Speaker: Sooyeong Kim
Affiliation: York University
Title: When does a random walker move around more rapidly?
Abstract: Kemeny's constant, a fundamental parameter in the theory of Markov chains, has recently received significant attention within the graph theory community. Originally defined for a discrete, finite, time-homogeneous, and irreducible Markov chain based on its stationary vector and mean first passage times, Kemeny's constant finds special relevance in the study of random walks on graphs. Kemeny's constant gives a measure of how quickly a random walker can move around a graph, and is thus a good measure of the connectivity of a graph. It is natural to study how graph structure informs a graph invariant. In this talk, we will understand how graph structures provide insights into Kemeny’s constant. In addition, we will also examine how the addition of an edge affects Kemeny’s constant.
Preprint | Recording passcode: .TApm94+ | Slides
29. March 8, 10am CT
Speaker: Leonardo de Lima
Affiliation: Federal University of Paraná (Brazil)
Title: On graphs with an eigenvector whose entries are only {-1,0,1}
Abstract: In 1986, Wilf posed the following question ``Which graphs have eigenvectors with entries solely -1 and +1?''. Stevanovic (2016) showed that the problem of finding such graphs is NP-Hard. Caputo, Khames, and Knippel (2019) described all graphs whose Laplacian matrix has an eigenvector with entries only -1 and +1 and apparently, they did not know Wilf's question related to the adjacency matrix. In this talk, we answer Wilf's question for the adjacency and the signless Laplacian matrix. Also, we give a characterization of all graphs having an eigenvector with entries only in {-1,0,1}. Our results point out an interesting relation of the graphs with these kinds of eigenvectors to the degree sequence of the graph.
Preprint | Recording passcode: ?0t64p*@ | Slides
30. March 22, 10am CT
Speaker: Alexander Farrugia
Affiliation: University of Malta Junior College
Title: On the Adjugate Matrix and the Polynomial Reconstruction Problem
Abstract: The adjugate matrix of a graph G on n vertices, denoted by adj G, is the adjugate of xI - A, where A is the 0-1 adjacency matrix of the graph. The entries of this matrix are polynomials in the variable x, of varying degrees. We shall first outline introductory results on the adjugate matrix, in the process noting that the diagonal entries of adj G are the characteristic polynomials of the n vertex-deleted subgraphs of G.
The Polynomial Reconstruction Problem asks if it is possible to deduce the characteristic polynomial of G from those of its vertex-deleted subgraphs. Last year, it was its 50th year anniversary since it was put forward for the first time by Cvetković in 1973, yet it has resisted proof (or the discovery of a counterexample) during all this time. In view of the previous paragraph, the problem may be restated as attempting to find the characteristic polynomial of G from the diagonal entries of adj G. We then extend this idea to successfully deduce the characteristic polynomial of G from various subsets of the entries of adj G, some of which include its diagonal entries, and others that don’t.
Preprint | Recording passcode: TG4RFB*= | Slides
31. April 5, 10am CT
Speaker: S. Ahmad Mojallal
Affiliation: Department of Mathematics and Statistics, University of Regina
Title: The q-analogue of zero forcing on threshold graphs
Abstract: Zero forcing is a combinatorial game played on a graph with the ultimate goal of changing the colour of all the vertices at a minimal cost. Originally this game was conceived as a one-player game, but later a two-player version was devised in-conjunction with studies on the inertia of a graph, and has become known as the q-analogue of zero forcing.
In this talk, we study and compute the q-analogue zero forcing number for threshold graphs.
Preprint | Recording passcode: HP=YtY73 | Slides
32. April 19, 10am CT
Speaker: Soffía Árnadóttir
Affiliation: Technical University of Denmark
Title: Groups and quantum isomorphisms
Abstract: In this talk, I will introduce group-invariant quantum latin squares and their connection to quantum isomorphisms. There will be some representation theory and finally, we will see a method of constructing Cayley graphs that are quantum isomorphic (although there is no guarantee that they will be non-isomorphic).
No preprint | Recording passcode: 6+ZZ%4us | Slides
33. May 3, 10am CT
Speaker: Harry Richman
Affiliation: Fred Hutch Cancer Center
Title: Tree distance matrices and their minors
Abstract: The distance matrix of a graph records the length of the shortest path between any two vertices. Graham and Pollak found that when the underlying graph is a tree, the determinant of the distance matrix satisfies a nice, simple formula. In particular, the determinant only depends on the number of vertices.
In some applications, such as phylogenetics, we have an underlying tree but our information is limited such that we only know the distance between "terminal" vertices. In this situation, the determinant of the restricted distance matrix is not quite so simple. However, we show that the Graham-Pollak theorem result can be generalized to this setting, where the formula involves counts of various rooted spanning forests. I will explain this formula with examples and give some ideas behind its proof, which involves potential theory.
No preprint | Recording passcode: 9&?2DT7S | Slides
34. May 17, 10am CT
Speaker: Minerva Catral
Affiliation: Xavier University
Title: Spectral properties of a structured sign pattern related to a system of second order ODEs
Abstract: A sign pattern (matrix) has entries in {+, -, 0}. We investigate eigenvalue properties of a sign pattern of order 2n where two of the blocks are prescribed sign patterns of order n, and the other two (order n) blocks are the positive diagonal sign pattern and the sign pattern consisting of all zeros. Such sign patterns arise from dynamical systems of second-order ordinary differential equations.