Réunion d'hiver SMC 2025

Toronto, 5 - 8 decembre 2025

Théorie algébrique des graphes : progrès et problèmes
Org: Homer De Vera (University of Manitoba), Chris Godsil (University of Waterloo) et Hermie Monterde (University of Regina)
[PDF]

JANE BREEN, Ontario Tech University Reinforcement learning for algebraic graph theory: parallelizing Wagner's approach [PDF]

In a recent paper by Wagner (see [1]), it was shown that using reinforcement learning with a cross-entropy approach, one can efficiently find or construct counterexamples to conjectured bounds in algebraic graph theory. This method was re-implemented in [2], and used to disprove several published conjectures in spectral graph theory. In this talk, I will discuss these algorithms and some applications, along with some adaptations to these approaches which may improve speed and efficiency.

This is joint work with Alix Bouffard.

[1] Adam Zsolt Wagner (2021). Constructions in combinatorics via neural networks. arXiv:2104.14516

[2] Mohammad Ghebleh, Salem Al-Yakoob, Ali Kanso, Dragan Stevanovic (2024). Reinforcement learning for graph theory, I. Reimplementation of Wagner's approach. arXiv:2403.18429

STEVE BUTLER, Iowa State University Cospectral constructions for the $q$-Laplacian matrix [PDF]

Given a graph we consider the q-Laplacian matrix described as $qD+A$ where $D$ is the diagonal matrix of degrees and $A$ is the adjacency matrix. By proper selection of $q$ we recover well known matrices ($q=0$ is the adjacency; $q=1$ is the signless Laplacian; $q=-1$ is, up to sign, the Laplacian).

It is known that there are graphs which are cospectral (same multiset of eigenvalues) for the $q$-Laplacian for arbitrary choice of $q$ (any regular cospectral pair suffices, but regularity is not needed). The goal of this talk is to highlight some pair of graphs which are cospectral for the $q$-Laplacian for only some specific values of $q$ and we show there are infinitely many values of which have a cospectral pair. One of our tools we will use is some generalization of Godsil-McKay switching.

JOHN BYRNE, University of Delaware Nonabelian Sidon sets and extremal problems on digraphs [PDF]

An $S_k$-set is a subset of a group whose $k$-tuples have distinct products. We give explicit constructions of large $S_k$-sets in the groups $\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)$ and of large $S_2$-sets in $\mathrm{Sym}(n)\times\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)\times\mathrm{Alt}(n)$, as well as some probabilistic constructions for 'nice' groups. We show that if $k$ is even and $\Gamma$ has a normal abelian subgroup with bounded index then any $S_k$-set has size at most $(1-\varepsilon)|\Gamma|^{1/k}.$ The $S_k$-sets are related to the following graph-theoretic problem: determine the largest possible minimum outdegree in a directed graph with no subgraph in $\{C_{2,2},\ldots,C_{k,k}\}$, where $C_{\ell,\ell}$ is the orientation of $C_{2\ell}$ with two maximal directed $\ell$-paths. Contrasting with undirected cycles, the extremal minimum outdegree for $\{C_{2,2},\ldots,C_{k,k}\}$ is much smaller than that for any $C_{\ell,\ell}$. We count the directed Hamilton cycles in one of our constructions to improve the upper bound for a problem on Hamilton paths posed by Cohen, Fachini, and K\"orner. Joint work with Michael Tait.

MICHAEL CAVERS, University of Toronto Scarborough Digraphs with few distinct eigenvalues [PDF]

Graphs with few adjacency eigenvalues have been well studied. This presentation concerns the analogous problem for digraphs (with loops permitted) whose adjacency matrices have few distinct eigenvalues. A spectral characterization is given for the strongly connected digraphs that have exactly two distinct eigenvalues and further structural results are presented.

This is joint work with Bobby Miraftab.

ADA CHAN, York University Type-II matrices [PDF]

An $n\times n$ complex matrix $W$ is a type-II matrix if, for $i,j=1,\ldots, n$, \begin{equation*} \sum_{k=1}^n \frac{W_{ik}}{W_{jk}} = n\delta_{ij}. \end{equation*} Important examples of type-II matrices include spin models and complex Hadamard matrices. From each type-II matrix, Nomura's construction gives a formally dual pair of association schemes. This talk gives a brief overview of the rich theory of type-II matrices with connections to association schemes, spin models, and some recent work on quantum symmetry of graphs.

HOMER DE VERA, University of Manitoba Minimizing Kemeny's constant for partial stochastic matrices with a single specified column [PDF]

Given a finite, discrete-time, time-homogeneous Markov chain on $n$ states with an irreducible transition matrix $T$, we may compute Kemeny's constant $\mathcal{K}(T)$ in terms of the eigenvalues of $T$. Kemeny's constant on such matrices may be interpreted in terms of the expected number of steps to get from a random initial state to a random destination state, and hence, may be viewed as average travel time on a network when the states of the Markov chain are viewed as vertices on a graph. We similarly define $\mathcal{K}(T)$ in terms of eigenvalues of a stochastic matrix $T$ having a single essential class, an extension of irreducible stochastic matrices. Suppose we have a partial stochastic matrix where some entries are specified and the rest are unspecified, how do we choose values for the unspecified entries so that the resulting stochastic matrix has a single essential class and $\mathcal{K}(T)$ is minimized? Steve Kirkland solved this question for partial stochastic matrices where the only specified entries are the diagonal entries and where the only specified entries are in a single row. In this talk, we present our results for the case where the only specified entries are in a single column. This is a work in progress with Prof. Kirkland.

CHRIS GODSIL, University of Waterloo Problems in Algebraic Combinatorics II [PDF]

Over 30 years ago I wrote a paper ``Problems in Algebraic Combinatorics'' (Elec. J. Comb.). I will report on successful resolution of three of these, lack of progress on others, and add some new ones.

HIMANSHU GUPTA, University of Regina Graph Complement and Delta Conjectures: Progress Using Classical Results [PDF]

Two major open problems in inverse eigenvalue problems for graphs concern the maximum nullity of matrices associated with graphs. Let $G$ be a graph of order $n$ and minimum degree $\delta$. The first asks whether the sum of maximum nullities of $G$ and its complement is lower bounded by $n-2$. The second asks whether the maximum nullity of $G$ is lower bounded by $\delta$. They are called the graph complement conjecture and the delta conjecture, respectively. In this talk, I present progress on both conjectures using classical results of Mader from 1972 and Lovasz, Saks, and Schrijver from 1989. This work is in collaboration with Francesco Barioli, Shaun M. Fallat, and Zhongshan Li.

ZILIN JIANG, Arizona State University Median eigenvalues of subcubic graphs [PDF]

We present a resolution to conjectures by Fowler, Pisanski, and Mohar regarding the median eigenvalues of subcubic (chemical) graphs. Specifically, we prove that the median eigenvalues of every connected graph with maximum degree at most three, except for the Heawood graph, lie within the interval [-1, 1]. This result has significant implications in mathematical chemistry, particularly in the analysis of molecular orbital models, and extends prior work on bipartite chemical graphs.

SOOYEONG KIM, University of Guelph A Nordhaus--Gaddum Problem for the Spectral Gap of a Graph [PDF]

We study how quickly a random walk on a graph mixes by examining the spectral gap of its transition probability matrix. For any graph $G$ on $n$ vertices and its complement $\overline{G}$, we prove that \[ \max\{\operatorname{gap}(G),\, \operatorname{gap}(\overline{G})\} = \Omega(1/n). \] When both the minimum and maximum degrees of $G$ are $\Omega(n)$, this maximum spectral gap improves to $\Theta(1)$. We also establish lower bounds of order $\Omega(1/n)$ when the maximum degree is $n - O(1)$, or when $G$ is the join of two graphs.

In contrast, we construct families of connected graphs whose complements are also connected for which \[ \max\{\operatorname{gap}(G),\, \operatorname{gap}(\overline{G})\} = O(n^{-3/4}). \] These results illustrate how complementary graph structures constrain spectral-gap behaviour.

STEVE KIRKLAND, University of Manitoba An edge centrality measure based on Kemeny's constant [PDF]

Given a connected graph $G$, Kemeny's constant $\kappa(G)$ is a parameter associated with the random walk on $G$ that measures how easily the random walker circulates through the vertices of $G$. We consider a measure of edge centrality $c(\bullet)$ that is based on Kemeny's constant. In the special case that $e$ is a cut edge of $G$ whose deletion yields the disconnected graph $G_1 \cup G_2,$ it turns out that $c(e)=\kappa(G)-\kappa(\widehat G_1)-\kappa(\widehat G_2),$ where $\widehat G_1$ (resp. $ \widehat G_2$) is formed from $G_1$ (resp. $ G_2$) by adding a loop at the vertex incident with $e$.

When $G$ is a tree, we produce a formula for $c(e)$ that is completely combinatorial. That formula yields attainable upper and lower bounds on $c(e)$ for trees, and facilitates an analysis of the behaviour of $c(e)$ when a branch of the tree is moved.

Joint work in progress with Max Wiebe.

HITESH KUMAR, Simon Fraser University Square Energy: Conjectures and Results [PDF]

For an $n$-vertex graph $G$ with adjacency eigenvalues $\lambda_1\ge \cdots \ge \lambda_n$, the positive square energy $s^+(G)$ and negative square energy $s^-(G)$ are defined as follows: \[ s^+(G)=\sum_{\lambda_i > 0} \lambda_i^2, \quad s^-(G)=\sum_{\lambda_i < 0} \lambda_i^2.\] In recent years, interesting results have been proved about the square energy of graphs, exciting generalizations have been made, but many questions remain open. In this talk, the speaker will present the state of the art on these parameters. Based on joint work with several authors: Saieed Akbari, Bojan Mohar, Shivaramakrishna Pragada, and Shengtong Zhang.

ALICE LACAZE-MASMONTEIL, University of Regina On the second largest eigenvalue of certain graphs in the perfect matching association scheme [PDF]

Defined as the difference between its two largest eigenvalues, the spectral gap of a graph plays an important role on our understanding of its connectivity as observed by Godsil and Royle (2001). Since computing the largest eigenvalue of a graph is generally not too difficult, the crux to understanding the spectral gap of a graph is to compute its second largest eigenvalue. In this talk, we will consider the spectral gap of certain graphs in the perfect matching association scheme. Since these graphs are part of the same association scheme, they have the same eigenspaces. These eigenspaces correspond to irreducible representations of the symmetric group and thus, one could use these irreducible representations to compute the eigenvalues of each graph. In practice, such computations are difficult to perform which makes it difficult to find the eigenspace that realizes the second largest eigenvalue. The focus of my talk will be to identify this eigenspace for selected graphs in the scheme. This is joint work with Himanshu Gupta, Allen Herman, Roghayeh (Mitra) Maleki, and Karen Meagher.

WILLIAM MARTIN, Worcester Polytechnic Institute The design strength of $P$- and $Q$-polynomial association schemes [PDF]

Let $\Gamma$ be a $Q$-polynomial distance-regular graph on vertex set $X$ and let $E_0,E_1,\ldots,E_d$ be a $Q$-polynomial ordering of the primitive idempotents of its Bose-Mesner algebra. If $E_1$ has rank $m$, then $\frac{|X|}{x}E_1$ is the Gram matrix of a spherical code in $\mathbb{R}^m$ and this is a spherical $t$-design for some $t\ge 2$. In this talk, we investigate the relationship between $t$ and the Krein parameters of the association scheme. In particular, we prove that, for $m>2$, we have $t\le 5$. This resolves a conjecture I made in 2013. This is work in progress with Jesse Lansdown (Galway), Akihiro Munemasa (Tohoku), Sho Suda (NDA Japan) and Hajime Tanaka (Tohoku).

BOBBY MIRAFTAB, Carleton University When the adjacency matrix of a graph is a product of two adjacency matrices? [PDF]

A graph G is factorizable via the matrix product if the adjacency matrix of G can be written as the product of two adjacency matrices. In this talk, we define the matrix product of two graphs, both algebraically and combinatorially, and identify families of simple graphs whose adjacency matrices admit such factorizations. We also show how spectral methods help characterize factorizable graphs.

HERMIE MONTERDE, University of Regina Equitable partitions and twin subgraphs [PDF]

In this talk, we prove a fundamental result about equitable partitions on weighted graphs with twin subgraphs, and use this result to construct graphs with pair and plus state transfer. In particular, for $\tau\in\{\frac{\pi}{2},\frac{\pi}{\sqrt{2}}\}$, we show that almost all connected planar graphs admit pair state transfer at time $\tau$, and almost all connected planar graphs can be assigned a single negative edge weight resulting in plus state transfer, or perfect state transfer between a plus state and a pair state, at time $\tau$. Using a result of Schwenk, analogous results will also be shown to hold for trees. This is joint work with Chris Godsil, Steve Kirkland, Sarojini Mohapatra, and Hiranmoy Pal.

JOY MORRIS, University of Lethbridge A new measure of EKR-robustness on permutation groups [PDF]

One of many questions that arises naturally out of extensions of the Erd\H{o}s-Ko-Rado Theorem, is the question of how many edges must be removed from a graph before the independence number increases. We study a variation on this question. The derangement graph of a permutation group is the Cayley graph on that group, whose connection set consists of all of the derangements in the group. Since we are dealing with Cayley graphs, rather than considering all subgraphs that can be produced by removing edges, we instead consider only subgraphs that are still Cayley graphs on the original group: that is, that can be produced by removing inverse-closed sets of elements (derangements) from the original connection set.

This is joint work with Karen Gunderson, Karen Meagher, Venkata Raghu Tej Pantangi, and Mahsa N. Shirazi.

JOHNNA PARENTEAU, University of Regina Determining Distinctness in the Weighted Matching Polynomial [PDF]

It is well known that the roots of any weighted matching polynomial of a graph with a Hamilton path are distinct, real numbers that enjoy a strict interlacing property with respect to the end-points of the Hamilton path. In this talk, we generalize this notion to establish a new class of graphs called $ { \rm SRSI}_w$ graphs. These graphs have simple roots where the roots of a vertex-deleted subgraph strictly interlace the roots of the graph. In this talk, we characterize all ${ \rm SRSI}_w$ graphs and provide a construction using a simple graph expansion operation.

SHIVARAM PRAGADA, Simon Fraser University Structure of Eigenvectors of Graphs [PDF]

Let $G$ be a graph on $n$ vertices with characteristic polynomial $\varphi_G(\lambda)$. A graph is said to be \emph{Irreducible} if the characteristic polynomial of its adjacency matrix is irreducible. For every irreducible graph $G$, we show that each eigenvector of its adjacency matrix has pairwise distinct, non-zero entries.

More generally, consider a graph $G$ whose characteristic polynomial factors over $\mathbb{Q}$ as \[ \varphi_G(\lambda)=p_1(\lambda)\cdots p_k(\lambda), \] where the polynomials $p_i(\lambda)$ are distinct irreducible factors. For any eigenvalue $\theta$ with minimal polynomial $p_j(\lambda)$, we prove a structure theorem of eigenspaces corresponding each polynomial $p_j(\lambda)$. We derive a lower bound on the number of distinct entries that must appear in every eigenvector corresponding to $\theta$.

It is conjectured that almost all graphs have irreducible characteristic polynomials, this has recently been confirmed under the assumption of the Extended Riemann Hypothesis. We pose new structural questions about irreducible graphs and present preliminary progress toward understanding their eigenvectors and spectral properties.

MARIIA SOBCHUK, University of Waterloo Quantum algorithms for matrix problems [PDF]

I will give an overview of recent progress in the area of quantum algorithms for matrix inversion with applications to solving certain kinds of differential equations.

TINO TAMON, Clarkson University How strong is weak coupling? [PDF]

Imagine a scenario (due to Bose) where Alice and Bob wish to send quantum bits to each other using a continuous-time quantum walk over a given graph which they view as a quantum channel. Against better judgment, they decide to attach weak edges (much like antennas) to the graph. We prove that this strategy works in creating high-fidelity quantum state transfer between them (under modest assumptions). As an added twist, this protocol is immune to localization.

This is joint work with Alastair Kay.

JOHN URSCHEL, MIT Nodal Statistics for Graphs and Matrices [PDF]

The study of discrete nodal statistics, that is, data regarding the zeros of Laplacian eigenvectors, provides insight into structural properties of graphs and matrices, and draws strong parallels with classical results in analysis for Laplacian eigenfunctions. In this talk, we will give an overview of the field, covering key results on nodal sets for graphs and their connection to known results and open problems in the continuous setting. In addition, we will discuss some recent progress towards a more complete understanding of the extremal properties of the nodal statistics of a matrix.

MERI ZAIMI, Perimeter Institute for Theoretical Physics Finite bivariate Tratnik functions [PDF]

In the context of algebraic combinatorics, $P$- and $Q$-polynomial association schemes are important objects which are closely related to distance-regular graphs. The polynomials appearing in these structures are classified by Leonard's theorem, and they belong to the discrete part of the ($q$-)Askey scheme. Moreover, the Terwilliger algebra of these schemes has been studied, and there are connections to the theory of Leonard pairs. In the recent years, progress has been made to extend these concepts to the case where the polynomials involved are multivariate. However, a classification analogous to Leonard's theorem is lacking in the mutlivariate case. With the purpose of progressing in that direction, I will discuss work concerning certain finite families of bivariate functions, said of Tratnik type, which are expressed as an intricate product of univariate polynomials of the ($q$-)Askey scheme. The goal is to classify such functions which satisfy some generalized bispectral properties, that is, two recurrence relations and two ($q$-)difference equations of certain types.

HARMONY ZHAN, Worcester Polytechnic Institute Laziness of quantum walks [PDF]

The trace of the average mixing matrix measures the laziness of a quantum walk: the larger trace, the more likely that the walker stays at home in the long run. We will explore the combinatorial aspects of this graph invariant, and identify the laziest walkers in some families of graphs. This is joint work with Amulya Mohan, Christino Tamon and Yichi Xu.

haut de la page