Eigenvalues and graphs
Org:
Karen Meagher and
Hermie Monterde (University of Regina)
[
PDF]
- LUDOVICK BOUTHAT, University of Delaware and University of Regina
- STEVE BUTLER, Iowa State University
Gluing via block similarity matrices for distance matrices [PDF]
-
A common method to form cospectral graphs is to glue two graphs on a common vertex. The justification is often carried out by the use of combinatorial interpretations of coefficients of characteristic polynomials that can be readily computed using sparseness of the related matrices. However, if the matrix is dense, e.g. a distance matrix, this approach does not work.
In this talk we will look at how to use block similarity matrices to form cospectral constructions via gluing which work for many classes of matrices, including the adjacency, Laplacian, signless Laplacian, distance, and generalized distance matrix.
This work is the culmination of two REU projects that happened at Iowa State University in recent years.
- HOMER DE VERA, University of Manitoba
- JAIME GARZA, University of Ottawa
- CHRIS GODSIL, University of Waterloo
- KRYSTAL GUO, University of Amsterdam
Perfect state transfer, Cayley presentations, and quantum hardware [PDF]
-
We study perfect state transfer (PST) on Cayley graphs. Bridging the classical theory of isomorphic Cayley graphs with quantum walks, we show that under mild hypotheses, Cayley graphs of groups with an abelian subgroup of index two, or of extraspecial $p$-groups with conjugacy-closed connection sets, are also Cayley graphs of abelian groups. Consequently, many known constructions of PST on dihedral, dicyclic, and extraspecial $2$-groups are actually non-abelian presentations of abelian Cayley graphs. Conversely, we prove that for odd prime powers $q \ge 5$, the $\mathrm{SL}(2,q)$ graphs of Pantangi and Sin admit no abelian Cayley presentation, giving the first provably non-abelian infinite family of Cayley graphs with PST. We also construct an infinite family of Cayley graphs with peak state transfer.
Finally, I will briefly discuss experiments implementing continuous-time quantum walks with perfect and peak state transfer on a 156-qubit IBM Heron quantum processor.
Based on joint works with Arnbjörg Soffía Árnadóttir (arXiv:2608.20476) and Priscilla Awuah (arXiv:2610.20855).
- MAX LEVIT, York University
- KAREN MEAGHER, University of Regina
- HERMIE MONTERDE, University of Regina
- CALVIN MORIER, York University
Fractional Revival Between Cospectral Vertices On Oriented Graphs [PDF]
-
Continuous-time quantum walks have been studied for their potential applications to general-purpose quantum computing. Perfect state transfer (PST) occurs when the quantum walk transfers the state of one Qbit $u$ to another Qbit $v$ at some time. Periodicity occurs when the state of $u$ is returned fully to $u$ at some time.
Fractional revival (FR) interpolates between these two phenomena, occurring when the initial state of Qbit $u$ is split among Qbits $u$ and $v$ according to the FR parameters $\alpha, \beta \in \mathbb{C}$, satisfying $|\alpha|^2 + |\beta|^2 = 1$:
$$ U(\tau) \mathbf{e}_u = \alpha \mathbf{e}_u + \beta \mathbf{e}_v. $$
We study FR in the case of oriented graphs, using a skew-symmetric Hamiltonian matrix $H=iS$. If we further demand that the vertices $u$ and $v$ are cospectral, then particularly nice behaviour emerges: the FR will reoccur periodically, with parameters $\alpha$ and $\beta$ changing each time according to a simple formula. Depending on the spectrum of the graph, this allows either periodicity at some multiple of the first FR time, or FR with parameters $\epsilon$-close to arbitrary desired parameters at some multiple of the first FR time. Examples of both behaviours will be shown.
- JOY MORRIS, University of Lethbridge
A Hilton-Milner theorem for unions of cliques [PDF]
-
The Hilton-Milner theorem tells us about the maximum size for a family of intersecting sets, under the condition that the intersection of the sets is nonempty. Recall that the Erd\H{o}s-Ko-Rado Theorem says that the absolute maximum size for a family of intersecting sets arises when the sets do all share a common element, so the Hilton-Milner theorem provides the best possible bound for any family that isn't just a subfamily of an EKR family. There is a significant gap between these bounds, which can prove very useful.
I will present more about this background, and discuss some recent results that involved producing a Hilton-Milner type theorem for independent sets in a union of cliques. This talk covers joint work with Karen Gunderson, Karen Meagher, Raghu Pantangi, and Mahsa Shirazi. Unfortunately for us, our results were pre-empted by a similar paper by Huajun Zhang and Huihui Zhang, which is available in Discrete Math.
- RAGHU PANTANGI
- JOHNNA PARENTEAU, University of Regina
- SAROBIDY RAZAFIMAHATRATRA, University of Lethbridge
On Ramanujan derangement graphs arising from linear groups of degree two [PDF]
-
Let $X$ be a connected non-bipartite $k$-regular graph on $n$ vertices with eigenvalues $\lambda_1> \lambda_2\geq \ldots\geq \lambda_n$, and let $\lambda(X):=\max\{ |\lambda_2|,|\lambda_n| \}$. The graph $X$ is called a Ramanujan graph if $\lambda(X) \leq 2\sqrt{k-1}$.
Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, the derangement graph $\Gamma_G$ is the graph whose vertex set is $G$, and two elements $g$ and $h$ of $G$ are adjacent if $hg^{-1}$ is a derangement, that is, a fixed-point-free permutation.
In this talk, we will show that $\Gamma_G$ is a Ramanujan graph for every subgroup $\operatorname{SL}_2(\mathbb{F}_q) \trianglelefteq G\leq \operatorname{GL}_2(\mathbb{F}_q)$ acting transitively on the non-zero vectors of $\mathbb{F}_q^2$ such that $[\operatorname{GL}_2(q):G]$ is odd.
This is based on joint work with Roghayeh Maleki.
- ALIREZA TALEBPOUR, University of Regina
- HARMONY ZHAN, Worcester Polytechnic Institute
© Canadian Mathematical Society