2023 CMS Winter Meeting

Montreal, Dec 1 - 4, 2023

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Current Trends in Matrices, Graphs and Computing
Org: Shaun Fallat, Seyed Ahmad Mojallal and Sandra Zilles (University of Regina)
[PDF]

ANTHONY BONATO, Toronto Metropolitan University How to cool a graph [PDF]

The spread of influence is a major topic in network science, where contagion spreads from vertex-to-vertex by prescribed rules. We consider a new such process called cooling, which spreads in graphs as slowly as possible. Cooling can be thought of as the dual to burning, which is a well-studied topic introduced a decade ago. We survey results on cooling, including bounds and exact values on graph families, and isoperimetric inequalities with applications to grids.

ADA CHAN, York University Quantum isomorphism and Hadamard graphs [PDF]

In 2020, Man\v{c}inska and Roberson prove that two graphs $G$ and $H$ are quantum isomorphic if and only if, for any planar graph $F$, the number of graph homomorphisms from $F$ to $G$ is equal to the number of graph homomorphisms from $F$ to $H$.

In this talk, we discuss the use of their remarkable characterization to show that any two Hadamard graphs of the same order are quantum isomorphic, and the research questions that arise from this result.

This is joint work with Bill Martin.

CHRIS GODSIL, University of Waterloo Periodicity of Oriented Cayley Graphs [PDF]

Let $X$ be an oriented graph on $n$ vertices. Its adjacency matrix $A$ is skew-symmetric, i.e., if $u,v\in V(X)$ and $uv$ is an arc in $X$, then $A_{u,v}=1$ and $A_{v,u}=-1$, and if neither $uv$ nor $vu$ is an arc in $X$ then $A_{u,v}=0$. As $A$ is skew-symmetric, $iA$ is Hermitian and the matrices \[ U(t) := \exp(-tA), \quad (t\in\mathbb{R}), \] are orthogonal. It follows that they determine a continuous quantum walk on ther vertices of $X$. We say a matrix is \textsl{flat} if its entries all have the same absolute value. A quantum walk admits \textsl{uniform mixing} at time $t$ if $U(t)$ is flat.

If an $n\times n$ unitary matrix is flat, the absolute values of its entries are equal to $1/\sqrt{n}$, and if $U(t)$ is real and flat, then $\sqrt{n}U(t)$ is a real Hadamard matrix. This provides one reason why we are interested in uniform mixing. We have been trying to characterize which oriented Cayley graphs of abelian groups admit uniform mixing. We have proved that if a Cayley graph admits uniform mixing, the matrix-valued function $U(t)$ is periodic, and that this holds if and only if the eigenvalues of $A$ are all integer multiples of $\sqrt{\Delta}$ for some (necessarily negative) square-free integer $\Delta$. We are able to characterize the possible connection sets of these Cayley graphs.

In my talk I will discuss some of these results, and the machinery used to derive them. This is all joint work with Xiaohong Zhang.

GENA HAHN, Universoté de Montréal Siblings, twins and self-embedded graphs [PDF]

Two graphs are siblings if one embeds into the other; twins are non-isomorphic siblings. Each of the siblings is clearly self-embedded. The conjecture (and its variants and generalisations) is that a countable graph has 0, $\aleph_0$, or $2^{\aleph_0}$ twins. An analysis of disconnected self-embedded graphs leads to a positive answer for many graphs. The conjecture has recently been disproved for trees in a long paper but there are many cases where the conjecture is true and many interesting cases open. In this talk we give a brief survey.

HAMED HATAMI, McGill University Littlestone dimension and online learnability of partial matrices [PDF]

Answering an open problem of Alon, Hanneke, Holzman, and Moran (FOCS'21), we show that there are partial Boolean matrices with finite Littlestone dimensions, but any completion of them to a full matrix has an infinite Littlestone dimension.

This result shows that the online learnability of a partial concept class is not always inherited from the learnability of some ``extension'' of it to a total concept class.

The proof uses the breakthrough result of Goos and its subsequent improvements that led to almost optimal super-polynomial bounds on the ``biclique partition number versus chromatic number'' problem of Alon, Saks, and Seymour.

The talk is based on a joint work with Ben Cheung, Pooya Hatami, and Kaave Hosseini.

NATHAN JOHNSTON, Mount Allison University Laplacian $\{-1,0,1\}$- and $\{-1,1\}$-diagonalizable graphs [PDF]

A graph is called "Laplacian integral" if the eigenvalues of its Laplacian matrix are all integers. We investigate the subset of these graphs whose Laplacian is furthermore diagonalized by a matrix with entries coming from a fixed set, with particular emphasis on the sets $\{-1,0,1\}$ or $\{-1,1\}$. Such graphs include as special cases the recently-investigated families of "Hadamard-diagonalizable" and "weakly Hadamard-diagonalizable" graphs. As a combinatorial tool to aid in our investigation, we introduce a family of vectors that we call "balanced", which generalize totally balanced partitions, regular sequences, and complete partitions.

KAMYAR KHODAMORADI, University of Regina Scatter Dimension and FPT Approximation Algorithms for Clustering [PDF]

In this talk, I will introduce you to a novel and intrinsic characteristic of metric spaces that we have dubbed `scatter dimension'. This notion has applications in designing approximation algorithms for clustering problems that run in parameterized time, i.e., those algorithms that are allowed to run super-polynomially in certain parameters of the given problem, often referred to as FPT approximations. The talk will be based on our recent work [Abbasi et al., FOCS 2023], in which we provide tight FPT approximation algorithms for a general class of clustering problems, known as General Norm k-Clustering, for a wide range of metric spaces. We achieve this by i) linking the running time of the algorithm to the scatter dimension of the metric class, and ii) showing appropriate upper bounds on the scatter dimension of such metrics. At the end, I will also mention open problems and directions for future research.

DAVID KRIBS, University of Guelph Chordal Graphs and Distinguishability of Quantum States [PDF]

In this talk, I’ll discuss a graph and matrix theoretic approach I’ve developed with collaborators for the problem of distinguishing quantum product states in the fundamental quantum communication framework called local operations and classical communication (LOCC). We have found that chordal graphs are the most important subgraph type when it comes to distinguishability in ‘one-way’ LOCC, and we have derived a one-way LOCC characterization for chordal graphs that establishes a connection with the theory of matrix completions. I’ll discuss our main results and some examples from our most recent work. This talk is based on joint work with Comfort Mintah, Michael Nathanson, Rajesh Pereira.

MANUEL LAFOND, Université de Sherbrooke Parameterized Graph Algorithms using Restricted Modular Partitions [PDF]

The modular-width of a graph is the maximum number of children of a node in the modular tree decomposition of the graph. Graphs with small modular-width are useful in solving algorithmic problems, since we can often solve the problem recursively on the modules, then use brute-force over the small set of modules to combine these solutions. This works as long as we are able to solve the problem efficiently in the modules themselves. Therefore, each module could be in any graph class that allows efficient algorithms. For a graph class $\mathcal{G}$, we thus define the $\mathcal{G}$-modular cardinality of a graph $G$ as the minimum size of a modular partition of $G$ into modules that belong to $\mathcal{G}$. We will discuss the complexity aspects of computing the $\mathcal{G}$-modular cardinality for a variety of graph classes, including cographs, cliques, edgeless graphs, and then discuss how it can be useful to design algorithms.

FARNAM MANSOURI, University of Waterloo What Forms of Collusion Can Be Avoided in Sample-Efficient Machine Teaching? [PDF]

In this presentation, we introduce the first batch machine teaching framework with sample complexity bounded by VC dimension.

The structure of the talk is as follows: We begin by introducing formal models for learning with a teacher and learning with random examples. Next, we explore the concept of VC dimension and its relationship to PAC-learnability. We then discuss the importance of ensuring a collusion-free environment in machine teaching to avoid coding tricks, and we address its limitations. Finally, we present our novel teaching complexity parameter, $STD_{min}$, and discuss its benefits.

WILLIAM MARTIN, Worcester Polytechnic Institute Four-class $Q$-bipartite association schemes [PDF]

A \emph{(symmetric) association scheme} can be viewed as a real subalgebra $\mathbb{A}$ of an algebra of square matrices over the reals in which every element is symmetric, which is closed under entrywise multiplication $\circ$ and contains both $I$ and $J$ (the matrix of all ones). Let $E$ be a matrix in $\mathbb{A}$ and, for $0\le j\le d = {\rm dim} \, \mathbb{A}$, denote by $E^{\circ j}$ the matrix whose entries are the $j^{\rm th}$ powers of the entries of $E$. We say the association scheme is \emph{$Q$-polynomial} (or \emph{co-metric}) with \emph{$Q$-polynomial generator} $E$ if the linear spans $\mathcal{I}_j= \langle J, E, \ldots, E^{\circ j} \rangle$ form a chain of ideals in $\mathbb{A}$ with $\mathcal{I}_d=\mathbb{A}$. It follows that $\mathbb{A}$ admits a vector space basis $E_0,E_1,\ldots, E_d$ with $E_i E_j = \delta_{i,j} E_i$ where $E_i$ is expressible as a polynomial of degree $i$ applied entrywise to $E$. In this talk, we focus on the \emph{$Q$-bipartite} case where $(E_i \circ E_j) E_k = 0$ whenever $i+j+k$ is odd. We specialize Schoenberg's Theorem to this case and apply it to certain families with $d=4$. The talk is mostly based on joint work with Brian Kodalen.

BOJAN MOHAR, SFU Extremal trees for eigenvalue combinations [PDF]

Let $\lambda_1(T)\ge \lambda_2(T)\ge \cdots \ge\lambda_n(T)$ be the eigenvalues of an $n$-vertex tree $T$. Trees for which $\lambda_1(T)$ or $\lambda_2(T)$ is largest or smallest possible among all $n$-vertex trees have been classified. In this talk the speaker will discuss extremal trees for linear combinations $\alpha\lambda_1(T)+\beta\lambda_2(T)$, where $\alpha,\beta\in \mathbb{R}$. This is joint work with Hitesh Kumar, Shivaramakrishna Pragada, and Harmony Zhan.

AHMAD MOJALLAL, University of Regina Forts, (fractional) zero forcing, and Cartesian products of graphs [PDF]

In this talk, we introduce the (disjoint) fort number, fractional zero forcing number, and fort hypergraph. The hypergraph results on transversals and matchings are applied to the zero forcing number and fort number. These results are used to establish a Vizing-like lower bound for the zero forcing number of a Cartesian product of graphs for certain families of graphs, and a family of graphs achieving this lower bound is exhibited.

HERMIE MONTERDE, University of Manitoba Quantum walks on join graphs [PDF]

Let $M$ be the adjacency or Laplacian matrix of a graph $X$. A quantum walk on $X$ is determined by the unitary matrix $U(t)=\exp(itM)$, whereby $|U(t)_{u,v}|^2$ is interpreted as the probability that a quantum state at vertex $u$ is found at vertex $v$ at time $t$. In particular, if $|U(\tau)_{u,v}|^2=1$, then we say that perfect state transfer occurs between $u$ and $v$ at time $\tau$.

The join $X\vee Y$ of two graphs $X$ and $Y$ is the graph obtained by joining each vertex of $X$ to each vertex of $Y$. In this talk, we discuss the properties of quantum walks on join graphs, with emphasis on perfect state transfer. Throughout, we rely on the spectral properties of join graphs relative to the adjacency and Laplacian matrix.

JOY MORRIS, University of Lethbridge Can we detect (Di)Graphical Regular Representations easily? [PDF]

Graphical and Digraphical Regular Representations (GRRs and DRRs) are a concrete way to visualise the regular action of a group, using (di)graphs. More precisely, a GRR or DRR on the group $G$ is a (di)graph whose automorphism group is isomorphic to the regular action of $G$ on itself by right-multiplication.

For a (di)graph to be a DRR or GRR on $G$, it must be a Cayley (di)graph on $G$. Whenever the group $G$ admits an automorphism that fixes the connection set of the Cayley (di)graph setwise, this induces a nontrivial graph automorphism that fixes the identity vertex, which means that the (di)graph is not a DRR or GRR. Checking whether or not there is any group automorphism that fixes a particular connection set can be done very quickly and easily compared with checking whether or not any nontrivial graph automorphism fixes some vertex, so it would be nice to know if there are circumstances under which the simpler test is enough to guarantee whether or not the Cayley graph is a GRR or DRR. I will present a number of results on this question.

This is based on joint work with Dave Morris and with Gabriel Verret.

TODD MULLEN, University of Prince Edward Island Pay it Backward [PDF]

Pay it Backward is a wealth-sharing model on graphs. However, Pay it Backward is a "bad" model as it often results in great wealth disparity. This model is used to illustrate the possibility of finding periodicity in aperiodicity. With a focus on the unexpected quirks of research, this talk will hopefully be of particular use for new researchers.

SHIVARAM PRAGADA, SIMON FRASER UNIVERSITY Subdivision and Adjacency spectra of Graphs [PDF]

Let $G$ be the a graph with $n$ vertices. Let $A(G)$ be its adjacency matrix. We denote the eigenvalues of $A(G)$ by $$\lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G).$$ Let $S \subseteq E(G).$ For $t\geq 1$, we define $G_t = G_t(S)$ to be the graph obtained from $G$ by replacing each edge $uv\in S$ with a path $P_{uv}$ of length $t$.

In this talk, we investigate the asymptotic nature of graph spectra when some edges of a graph are subdivided sufficiently many times. We show that, for a fixed $k$, the sequence $\{\lambda_k(G_t)\}_{t=0,1,2,\dots}$ is a Cauchy sequence.

This is a joint work with Hitesh Kumar, Bojan Mohar and Hanmeng Zhan.

BEN SEAMONE, Dawson College Defective acyclic colourings of planar graphs [PDF]

A vertex colouring of a graph $G$ is called acyclic if the colouring is proper and any two colour classes induce an acyclic subgraph of $G$. It was shown by Borodin (1979) that every planar graph has an acyclic $5$-colouring. Mondal, Nishat, Rahman, and Whitesides (2013) show that any planar triangulation can be made acyclically $3$-colourable by subdividing $2n-5$ of its edges exactly once each, and acyclically $4$-colourable by subdividing $\frac{3}{2}n-\frac{7}{2}$ of its edges exactly once each. We extend and complement these results by providing bounds on the number of edges whose deletion will make a planar graph acyclically $3$-colourable or $4$-colourable, and providing tight bounds on the minimum number of edges one needs to remove from a planar graph in order to turn any proper $3$-colouring or $4$-colouring into an acyclic colouring. Joint work with On-Hei Solomon Lo and Xuding Zhu.

MAHSA N. SHIRAZI, University of Manitoba Uniform hypergraphs and balanced incomplete block designs with r-friendship property [PDF]

A $t$-uniform hypergraph $\mathcal{H}$ has $r$-friendship property if for every $t$-subset of vertices $v_{1}, \dots, v_{t}$, there are exactly $r$ vertices $w_{1}, \dots, w_{r}$ such that for $(t-1)$-subsets $A$ of vertices $v_{i}$, and any $w_{i}$, $A\cup \{w_{i} \}$ is a hyperedge in $\mathcal{H}$. Li et al. conjectured that no balanced incomplete block design (BIBD) has $1$-friendship property. We show that if $\mathcal{H}$ is a $1$-friendship $t$-uniform hypergraph that is a BIBD-$(n,b,d,t,\lambda)$, then $n$ is small enough with respect to $\lambda$. Furthermore, we present a class of $1$-friendship $t$-uniform hypergraph that is a BIBD. We generalize our results to $r$-friendship $t$-uniform hypergraph and show no such hypergraphs are BIBD when $n$ is large enough with respect to $\lambda, t,$ and $r$.

MICHAEL TAIT, Villanova University The largest eigenvalue of the normalized distance Laplacian matrix [PDF]

We discuss two conjectures of Reinhart which seek to minimize or maximize the largest eigenvalue of the normalized distance Laplacian matrix over all connected $n$ vertex graphs. We prove one of these conjectures and make significant progress towards the second. If $\lambda$ is the largest eigenvalue over all normalized distance Laplacians of $n$ vertex connected graphs, then $\lambda = 2 - \Theta\left(\frac{1}{\sqrt{n}} \right)$. We show that under any one of several natural conditions, the extremal graph must have diameter $\Theta\left( \sqrt{n} \right)$.

JEREMIE TURCOTTE, McGill University On an induced version of Menger's theorem [PDF]

Menger's theorem is one of the most fundamental results in graph theory: if $G$ is a graph, either $A,B\subseteq V(G)$ can be separated by removing fewer than $k$ vertices, or there exists $k$ pairwise disjoint $A\text{-}B$ paths. What happens if we wish these paths to not only be disjoint, but non-adjacent? This question, while interesting in its own right, is also motivated by the Coarse Graph Theory recently proposed by Georgakopoulos and Papasoglu. We show the existence of a constant $C$, which depends only on the maximum degree of $G$, such that either $A,B$ can be separated by removing at most $Ck$ vertices, or there exists $k$ pairwise non-adjacent $A\text{-}B$ paths. A generalization of this result to graphs with a forbidden topological minor will also be discussed, as well as more precise results for the subcubic case. Joint work with Kevin Hendrey, Sergey Norin and Raphael Steiner.

top of page