Réunion d'hiver SMC 2022

Toronto, 2 - 5 décembre 2022

Théorie algébrique et spectrale des graphes
Org: Jane Breen (Ontario Tech), Sooyeong Kim (York), Hermie Monterde (Manitoba) et Xiaohong Zhang (Waterloo)
[PDF]

ROBERT F. BAILEY, Grenfell Campus, Memorial University Cataloguing strongly regular graphs with primitive automorphism groups [PDF]

A graph is strongly regular with parameters $(n,k,\lambda,\mu)$ if it has $n$ vertices, is $k$-regular, and two vertices have either $\lambda$ or $\mu$ common neighbours depending on whether or not they are adjacent. This is equivalent to a $k$-regular graph having exactly three eigenvalues, namely $k$ and two others which can be calculated explicitly from the parameters, as can their multiplicities.

Many well-known examples of strongly regular graphs arise from group actions. The GAP computer algebra system contains libraries of primitive groups (i.e. those which preserve no interesting equivalence relations) on up to 4095 points. We discuss a detailed analysis of these libraries to catalogue the strongly regular graphs (and the more general class of distance-regular graphs) which arise from these groups: while most of the graphs were already known, a few surprises which came up along the way, and some interesting questions (both theoretical and computational) remain open.

This is joint work with my NSERC USRA students Alaina Pardy and Abigail Rowsell.

STEVE BUTLER, Iowa State University Complements of coalescing sets [PDF]

Given graphs $H_1, H_2$ with $B_1\subseteq V(H_1), B_1\subseteq V(H_1)$ we way that $(H_1,B_1)$ and $(H_2,B_2)$ are coalescing cospectral if attaching any rooted graph $G$ onto the vertices of $B_1$ in $H_1$ and onto the vertices of $B_2$ in $H_2$ always results in cospectral graphs (with respect to some designated matrix associated with the graphs, e.g. adjacency, Laplacian, ...); we denote this by $(H_1,B_1)\sim(H_2,B_2)$. Our main result is to show that for many standard matrices (adjacency, Laplacian, signless Laplacian) that $(H_1,B_1)\sim(H_2,B_2)$ if and only if $(H_1,\overline{B_1})\sim(H_2,\overline{B_2})$. As an application we will look at cospectral trees and non-trees for the signless Laplacian matrix.

MICHAEL CAVERS, University of Toronto Scarborough Spectra of sign patterns [PDF]

A sign pattern is a matrix with entries in $\{+,-,0\}$. To every square sign pattern there is a corresponding signed directed graph. We discuss different spectral properties a square sign pattern can have along with the restrictions these properties imply on the structure of the corresponding signed digraph. Techniques employed in this area are outlined.

QIUTING CHEN, University of Waterloo Bipartite walks are better than Grover's walk [PDF]

We introduce a new discrete quantum walk model, known as bipartite walks. We show that Grover's walk is a special case of bipartite walks. Using the connections between the spectrum of a graph $G$ and the spectrum of the subdivision graph of $G$, we show that when $G$ is a regular bipartite graph, one step of bipartite walk defined over $G$ is two steps of Grover's walk defined over $G$.

SHAUN FALLAT, University of Regina Revisiting the Parter-Wiener Theorem [PDF]

The celebrated Parter-Wiener theorem is an important result concerning the multiplicities of eigenvalues associated with trees. The theorem essentially verifies the existence of a vertex in a tree whose deletion increases the multiplicity of a given eigenvalue under certain conditions. In this presentation, we revisit the proof of this result and establish both the classical theorem and a known extension using the notion of the Schur-complement. We will also explore some related implications using both the Schur-complement and other basic matrix theory. This work represents joint work with an NSERC-USRA, Johnna Parenteau.

CHRIS GODSIL, University of Waterloo State transfer on big graphs [PDF]

Childs and colleagues have made use of continuous quantum walk on infinite graphs, obtained by merging infinite paths onto some vertices of a finite graph.This works raises questions about state transfer on such graphs. I have proved that perfect state transfer cannot occur on a connected infinite graph with bounded valency. I will discuss some of the components of this proof, and of some related results.

LORD KAVI, University of Ottawa $3$-independence number of graphs [PDF]

We present a spectral bound on the $3$-independence number of graphs and apply this bound to well-known families of graphs. We investigate tightness of this bound on the Hamming graph $H(d,q)$. In particular, we give a construction of $3$-independent sets in $H(d,2)$ and show tightness of the bound for $d=2^r$ and $d=2^r-1$ with $r\in \mathbb Z^+$.

MARK KEMPTON, Brigham Young University Isospectral Reductions and Quantum Walks [PDF]

The isospectral reduction of a graph to a subset of its vertex set is a way to produce a smaller, function-weighted graph preserving spectral properties. Recently, cospectral vertices were characterized by isospectral reductions. In this talk, we will discuss this result and follow-up work that shows even stronger connections to the quantum walk matrix.

PAULA KIMMERLING, Washington State University Rank of Average Mixing Matrix in Dutch Windmill Graphs [PDF]

Let $X$ be a graph. We associate this graph with a continuous-time quantum walk by using a transition matrix $U(t) = \exp{itA}$, where $A$ is the adjacency matrix. This allows us to create the average mixing matrix $\hat{M}$ which is time-independent and gives some sense of average probability values and long-term behavior. $\hat{M}$ has previously been studied on trees and graphs with distinct eigenvalues. Our focus is on Dutch Windmill graphs which all have repeated eigenvalues. In this talk we will show that $\hat{M}$ has "half-rank" and why, including the relationships between the spectra of Dutch Windmill graphs and path/star graphs.

STEVE KIRKLAND, University of Manitoba Kemeny's constant for an undirected graph: how much can adding one edge change things? [PDF]

Given a connected graph $G$, we consider the corresponding random walk, described as follows. Our random walker moves from one vertex to another in discrete time; when the walker is on vertex $v$ at time $t$, one of the neighbours of $v$, say $v'$, is chosen at random, and the walker moves to vertex $v'$ at time $t+1$. The expected time it takes for the random walker to move from a randomly chosen initial vertex to a randomly chosen destination vertex is known as Kemeny's constant, and it can be thought of as measuring the random walker's ease of movement through the graph.

What happens to Kemeny's constant when a new edge is added to $G$? It turns out that, depending on the structure of the graph and the placement of the new edge, Kemeny's constant might increase, or decrease, or stay the same. In this talk we take a step towards quantifying this behaviour. For each natural number $n$, we consider the family of trees on $n$ vertices. We identify the tree in that family, as well as the new edge to be added, so that the increase in Kemeny's constant is maximized. We also solve the corresponding problem for maximizing the decrease in Kemeny's constant. The techniques rely on a detailed analysis of distance matrices for trees.

PRATEEK VISHWAKARMA KUMAR, University of Regina The Gantmacher--Krein determinantal inequalities via planar networks [PDF]

Gantmacher and Krein discovered a relation between the determinant of a totally nonnegative matrix and its partial Laplace expansions along the first row using Sylvester's determinant identity. We shall present an alternate proof of the same using the re-parameterization of totally nonnegative matrices in terms of weighted acyclic directed planar networks, which is popularly known as the converse of Lindström's lemma. To conclude, we shall articulate some of the outcomes of employing this method in related and ongoing work with Shaun Fallat.

SABRINA LATO, University of Waterloo Characterizations of Distance-Biregular Graphs and Related Problems [PDF]

Fiol, Garriga, and Yebra developed a couple of characterizations of distance-regular graphs based on the existence of a polynomial with specific properties. We extend their characterizations to distance-biregular graphs and show how these characterizations can be used to study bipartite graphs with distance-regular halved graphs and graphs with the spectrum of a distance-biregular graph.

MAXWELL LEVIT, University of Waterloo Covers of Graphs from Extensions of Groups [PDF]

For each $n$-cube, there is a graph on twice as many vertices which covers (in a mildly technical sense which we will discuss) the $n$-cube but contains no 4-cycles. There is a lot to say about these graphs: They originated in a uniqueness proof for certain generalized hexagons. They appear implicitly in Haung's resolution of the Sensitivity Conjecture. And they demonstrate a nice correspondence between covers of Cayley graphs and extensions of groups which I have had some success in exploring. I will discuss these graphs and these contexts.

GABOR LIPPNER, Northeastern University Pretty Good Fractional Revival via diagonal perturbation [PDF]

Continuing our study of the effect of magnetic fields on state transfer, in this talk we focus on Pretty Good Fractional Revival (PGFR) in the setting of continuous time quantum walks on graphs. Fractional Revival is a generalization of Perfect State Transfer, in which the walk, at a specific time, is required to return to a fixed "starting subset" of nodes with probability 1. PGFR is then the usual asymptotic relaxation where only the supremum of this probability (as time goes to infinity) needs to be 1.

We develop the requisite spectral and number-theoretic tools to prove PGFR under a generic diagonal perturbation (aka magnetic field) and show how to construct examples of PGFR based on this theory. A key point is that we are able to generalize everything to subsets of more than 2 nodes, which would be the standard setting for state transfer.

Joint work with Mark Kempton.

SEYED AHMAD MOJALLAL, University of Regina Distribution of Laplacian eigenvalues of graphs [PDF]

Let $G$ be a graph of order $n$ with $m$ edges. Also let $\mu_1\geq \mu_2\geq \cdots\geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of graph $G$ and let $\sigma=\sigma(G)$ $(1\leq \sigma\leq n)$ be the largest positive integer such that $\mu_{\sigma}\geq \frac{2m}{n}$. In this talk, we show that $\mu_2(G)\geq \frac{2m}{n}$ for almost all graphs. Moreover, we characterize the extremal graphs for any graphs. We also provide the answer to Problem 3 in [Distribution of Laplacian eigenvalues of graphs, Linear Algebra Appl. 508 (2016), 48--61], that is, the characterization of all graphs with $\sigma=1$. Moreover, we present a few relations between $\sigma$ and other graph invariants, in particular, we give a Nordhaus–Gaddum-type result for $\sigma$.

HERMIE MONTERDE, University of Manitoba Fractional revival between twin vertices [PDF]

Fractional revival is a generalization of perfect state transfer. But unlike perfect state transfer, fractional revival is a relatively unexplored quantum phenomenon. In this talk, we will discuss the existence of fractional revival between twin vertices.

YUJIA SHI, Northeastern University Achieving strong state transfer using a bounded potential [PDF]

Considering each particle of an n-qubit system as a vertex, we can describe quantum transport phenomena using graphs. The probability of transferring the state of node $u$ to node $v$ at time $t$ is given by $p(t) = \langle u|e^{itH}|v\rangle^2$. Here the Hamiltonian, $H$, of this system corresponds to the adjacency matrix and energy potential.

Assume the graph has an involution $T$ and the potential takes value $Q$ on nodes $u$ and $v=Tu$ and 0 elsewhere. In this setting Lin, Lippner, and Yau have shown that there is asymptotic state transfer, that is, $\sup_t p(t) \rightarrow 1$ as $Q$ goes to infinity. Kirkland and van Bommel recently proved a strong quantitative version of this result when the graph is a path with endpoints $u$ and $v$.

In this talk, I will discuss a generalization of the Kirkland - van Bommel bound to arbitrary graphs with an involution. By studying approximate eigenvectors of the Hamiltonian, we get quantitative bounds on the potential that guarantees asymptotic state transfer. Remarkably, these bounds depend only on the maximum degree of the graph and not its size.

Joint work with Gabor Lippner.

MAHSA SHIRAZI, University of Manitoba Graphs with $r$-friendship property [PDF]

For $r\geq 1$, a graph has $r$-friendship property if every pair of vertices has exactly $r$ common neighbours. The motivation for this definition is from the Friendship theorem, which is on the graphs with $1$-friendship property. The Friendship theorem, first proved by Erdős, Rényi, and Sós in 1966, states that if $G$ is a graph in which every pair of vertices has exactly one common neighbour, then $G$ has a universal vertex $v$ adjacent to all others, and the graph induced by $V(G)\setminus \{v \}$ is a matching. In this presentation, we study graphs with $r$-friendship property, where $r\geq 2$. We show all such graphs are strongly regular. Furthermore, we prove that for any $r\geq 2$, there are only finitely many graphs with $r$-friendship property. This is an ongoing joint work with Karen Gunderson.

MARIIA SOBCHUK, University of Waterloo Quantum isomorphisms [PDF]

You will learn about quantum isomorphism and recent developments in this area.

WANTING SUN, University of Waterloo Perfect Laplacian state transfer in graphs [PDF]

Let $X$ be a graph with Laplacian matrix $L$. We study continuous quantum walks on $X$ defined by the transition matrix $U(t)=\exp(itL)$. Assume that $Y$ is a graph whose vertex set is equal to $V(X)$. The Laplacian state associated with $Y$ is defined as $\frac{1}{2|E(Y)|}L(Y)$. Particularly, when $K_2$ (resp. $K_3$) is the unique non-trivial component of $Y$, we denote the Laplacian state associated with $Y$ by pair state (resp. triangle state) of $Y$. In this talk, we investigate the existence of perfect Laplacian state transfer in threshold graphs and strongly regular graphs. Firstly, we characterize all connected threshold graphs having perfect pair state transfer. Then we prove that a strongly regular graph $X$ on $n$ vertices admits perfect pair state transfer (resp. perfect triangle state transfer) if and only if $X$ is isomorphic to $\frac{n}{2}K_2$ or $\overline{\frac{n}{2}K_2}$. This is a joint work with Ada Chan, Qiuting Chen, Chris Godsil and Xiaohong Zhang.

CHRISTOPHER VAN BOMMEL, University of Manitoba Perfect State Transfer on Trees with Small Diameter [PDF]

Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. This transmission can be implemented by spin chains, which can be modeled as a graph, and analyzed using algebraic graph theory. We investigate the possibility of perfect state transfer on trees with small diameter, showing it is impossible for trees of diameter 4, and discussing progress for trees of diameter 5. Joint work with Steve Kirkland.

LUC VINET, IVADO/CRM Bivariate $P$-polynomial association schemes [PDF]

We offer a generalization of $P$-polynomial association schemes to situations where the underlying univariate polynomial families are replaced by bivariate polynomials. Examples of association schemes that fit the proposed framework are presented.

Based on work done in collaboration with Pierre-Antoine Bernard, Nicolas Crampé, Loïc Poulain D'Andecy and Meri Zaimi.

WEICHEN XIE, Clarkson University Breaking the Perfect State Transfer Speed Limit [PDF]

We describe a protocol for breaking the speed limit of perfect state transfer on quantum spin chains. The simple protocol relies on a fundamental application of fractional revival and dual-rail encoding. It offers a rare glimpse of the anti-Zeno effect at work in quantum state transfer. This is joint work with Alastair Kay and Christino Tamon.

HARMONY ZHAN, Simon Fraser University The second largest eigenvalue of a tree [PDF]

I will talk about the second largest eigenvalue of a tree with prescribed number of vertices and diameter. In particular, any tree that maximizes the second largest eigenvalue in this family must be a caterpillar with at most two bouquets. This is joint work in progress with Kumar, Mohar and Pragada.

XIAOHONG ZHANG, Université de Montréal Constructing cospectral graphs [PDF]

In this talk, we present a way to construct families of graphs that are pairwise cospectral with respect to the adjacency, Laplacian, unsigned Laplacian, and normalized Laplacian matrices. For example, with this construction, we obtain a family of 373 graphs on 25 vertices, all cospectral with respect to the above four matrices.

haut de la page