Réunion d'hiver SMC 2017
Waterloo, 8 - 11 décembre 2017
- ADA CHAN, York University
Quantum walks in association schemes [PDF]
-
The continuous-time quantum walk on a graph $X$ is given by the unitary operator $e^{-itA}$,
where $A$ is the adjacency matrix of $X$.
The graph $X$ admits fractional revival from $u$ to $v$ at time $\tau$ if
\begin{equation*}
e^{-i\tau A} = \alpha e_u+\beta e_v,
\end{equation*}
for some $\alpha, \beta \in {\mathbb C}$. Here $e_u$ and $e_v$ denote the characteristic vectors of vertices $u$ and $v$, respectively.
Perfect state transfer from $u$ to $v$ and periodicity at $u$ are two special cases of fractional revival with $\alpha=0$ and $\beta=0$, respectively. These two properties have been extensively studied but not so much for fractional revival when both $\alpha$ and $\beta$ are nonzero.
Instantaneous uniform mixing is another interesting phenomenon of the continuous-time quantum walk on a graph. This happens when $\sqrt{n} e^{-i\tau A}$ is a complex Hadamard matrix.
In this talk, we look for graphs in association schemes that satisfy one or more of these phenomena.
- BRIAN KODALEN, Worcester Polytechnic Institute
Linked Simplices [PDF]
-
Let $X$ and $Y$ be sets of unit vectors corresponding to regular simplices in $\mathbb{R}^v$ ($v+1$ vectors with pairwise inner product $-\frac{1}{v}$). We call $X$ and $Y$ a pair of linked simplices if, for every $x\in X$ and $y\in Y$, we have $\langle x,y\rangle \in \left\{\gamma,\zeta\right\}$ for some fixed values of $\gamma$ and $\zeta$. We ask the question of when you can find large sets of simplices for which every pair of them are linked using the same inner products $\gamma$ and $\zeta$. In this talk, we show that any set of $w$ linked simplices corresponds to a linked system of symmetric designs (LSSD) on $w$ fibers. Using the $Q$-polynomial structure of LSSDs, we then construct linked simplices showing the equivalence between these two objects. Finally we review known examples such as the Cameron-Seidel association scheme and, in restricted cases, use the linked simplices to construct real mutually unbiased bases.
- BILL MARTIN, Worcester Polytechnic Institute
Some recent results on Q-polynomial (cometric) association schemes [PDF]
-
Let $X$ be a finite set of size $v$ and let $\mathcal{R} = \{ R_0, \ldots, R_d\}$ be a partition of $X\times X$ into $d+1$
symmetric binary relations with $R_0$ equal to the identity relation on $X$.
The pair $(X,\mathcal{R})$ is called a symmetric $d$-class association scheme provided there exist integers
$p_{ij}^k$
($0\le i,j,k \le d$) such that whenever $a,b\in X$ with $(a,b)\in R_k$, we have
$ \left| \{ c \in X \ : \ (a,c)\in R_i , \ (c,b) \in R_j \} \right| = p_{ij}^k$. If $A_i$
is the 01-matrix with rows and columns indexed by $X$ and $(a,b)$-entry equal to one iff $(a,b)\in R_i$,
then the Bose-Mesner algebra of the association scheme is given by $\mathbb{A} = \langle A_0,\ldots,
A_d\rangle$. This matrix algebra admits a basis
$\{ E_0, E_1, \ldots, E_d\}$ satisfying $E_i E_j = \delta_{i,j} E_i$. The Schur (or entrywise) product of any
two of these idempotents belongs to $\mathbb{A}$ so there exist scalars $q_{ij}^k$ ($0\le i, j,k\le d$)
satisfying
\begin{equation}
E_i \circ E_j = \frac{1}{v} \sum_{k=0}^d q_{ij}^k E_k ~.
\end{equation}
An association scheme $(X,\mathcal{R})$ is cometric (or $Q$-polynomial) if there exists an ordering $E_0,\ldots, E_d$ with respect to which $q_{ij}^k = 0$ whenever $k > i+j$, and $q_{ij}^k \neq 0$ whenever $k=i+j$.
In this talk, we explore the spherical code formed by the columns of $E_1$ and establish inequalities for certain valencies of the (regular) graphs $(X,R_i)$ and the class number $d$ in terms of its rank.
- MATT MCGINNIS, University of Delaware
The smallest eigenvalues of Hamming and Johnson graphs [PDF]
-
We prove a conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-$j$) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-$j$) Johnson graphs. This is joint work with Andries Brouwer, Sebastian Cioab\u{a} and Ferdinand Ihringer.
- KAREN MEAGHER, University of Regina
An Erd\H{o}s-Ko-Rado theorem for 2-Transitive Groups [PDF]
-
The \textsl{derangement graph} for a group $G$ is a Cayley graph on $G$ with connection set the set of all derangements in $G$ (these are the elements with no fixed points). The eigenvalues of the derangement graph can be calculated using the irreducible characters of the group. The eigenvalues can give information about the graph, I am particularly interested in applying Hoffman's ratio bound to bound the size of the cocliques in the derangment graph for 2-transitive groups.
This is of intersect since it can be used to prove a version of the Erd\H{o}s-Ko-Rado theorem for 2-transitive groups. Two permutations are said to be \textsl{intersecting} if the permutations both map some $i$ to some $j$. A set of permutations is \textsl{intersecting} if any two permutations in the set are intersecting. The stabilizer of a point (or any coset of the stabilizer of a point) is an intersecting set.
The derangement graph of a group $G$ is defined so that the cocliques are exactly the sets of intersecting permutations from $G$. I will outline how Hoffman's ratio bound on the derangement graphs for 2-transitive graphs can be used to show that the largest set of intersecting permutations from a 2-transitive group is no larger than the stabilizer of a point. I will also present a conjectures about the structure of the cocliques in the derangement graphs for 2-transitive groups.
- JOY MORRIS, University of Lethbridge
Cayley index and Most Rigid Representations (MRRs) [PDF]
-
For any finite group $G$, a natural question to ask is the order of the smallest possible automorphism group for a Cayley graph on $G$. A particular Cayley graph whose automorphism group has this order is referred to as an MRR (Most Rigid Representation), and its Cayley index is the index of the regular representation of $G$ in the automorphism group. Study of GRRs (Graphical Regular Representations, where the full automorphism group is the regular representation of $G$) showed that with the exception of two infinite families and ten individual groups, every group admits a Cayley graph whose MRRs are GRRs, so that the Cayley index is $1$. I will present results that complete the determination of the Cayley index for those groups whose Cayley index is greater than $1$. This is based on joint work with Josh Tymburski.
- DANNY RORABAUGH, Queen's University
Graph Labelling with Combinatorial Nullstellensatz [PDF]
-
Combinatorial Nullstellensatz is an algebraic technique developed by Alon and Tarsi in 1992. Alon named this method in 2001 when he demonstrated its applicability to a wide range of problems in additive number theory and graph theory. This is an early instance of what is now called the Polynomial Method, a general approach for applying algebraic geometry to solve problems in discrete mathematics. Roughly speaking, by strategically associating a set of discrete objects with a polynomial, one can utilize algebraic properties of the Nullstellen (zero locus). This talk will focus on applications of Combinatorial Nullstellensatz to graph labelling problems.
- JOHN SINKOVIC, University of Waterloo
The inertia bound of a graph [PDF]
-
The inertia bound is an upperbound on the independence number of a graph. Attributed to D.M. Cvetkovi\'c, and sometimes referred to as the Cvetkovi\'c bound, it uses eigenvalues of adjacency-like matrices. It was shown recently that graphs exist for which this bound is not tight. We share some results from a recent undergraduate research project focused on finding such graphs. This is joint work with University of Waterloo undergraduate Zach Dockstader.
- MICHAEL TAIT, Carnegie Mellon University
7 theorems in extremal spectral graph theory [PDF]
-
Theorems in extremal graph theory ask to optimize a combinatorial invariant over a fixed family of graphs. In this talk, we discuss how to prove several theorems in this area where the graph invariant in question is a function of the eigenvalues or eigenvectors of the adjacency matrix of the graph. A representative result we will discuss is a proof of a conjecture of Boots and Royle from 1991: the planar graph of maximum spectral radius (of its adjacency matrix) is the join of an edge and a path. This is joint work with Josh Tobin.
- CLAUDE TARDIF, Royal Military College of Canada
Bounding chromatic numbers by solving linear equations [PDF]
-
We present systems of linear equations associated to a graph, with the property that if such a system is consistent, then the chromatic number of the graph is at least some given bound. We show how such systems are connected to the subject of topological bounds on the chromatic number of a graph.
This is joint work with Gord Simons and David Wehlau.
- DAVID WAGNER, University of Waterloo
Results on chromatic polynomials inspired by a correlation inequality of Farr [PDF]
-
In 1993, Graham Farr published a correlation inequality for chromatic polynomials of graphs, and made a number of much stronger conjectures. Inspired by this, we found a direct combinatorial proof of this inequality and began investigating a two-variable power series encoding the relevant information about a graph. I will report on various results, conjectures, and counterexamples regarding this series. This is joint work with Ghislain McKay.
- QING XIANG, University of Delaware
The Smith group of the hypercube graph [PDF]
-
The $n$-cube graph $Q_n$ is the graph on the vertex set of $n$-tuples of $0$s and $1$s, with two vertices joined by an edge if and only if the $n$-tuples differ in exactly one component. I will talk about the recent complete determination of the Smith group of $Q_n$, or, equivalently, the
elementary divisors of an adjacency matrix $A$ of $Q_n$. It would be of interest to find a diagonal form for the Laplacian matrix $nI-A$ of $Q_n$. The talk is based on joint work with David Chandler and Peter Sin.
- KAREN YEATS, University of Waterloo
On the $c_2$ invariant of a graph [PDF]
-
The $c_2$ invariant of a graph is an arithmetic invariant defined from the Kirchhoff polynomial of the graph. I will explain what it is and why it is interesting and briefly discuss some recent partial progress on a conjecture about one of its symmetries.
- HANMENG ZHAN, University of Waterloo
Discrete-Time Quantum Walks and Graph Embeddings [PDF]
-
A discrete-time quantum walk is determined by a unitary matrix $U$ that acts on the arcs of a graph. For most of the existing models, the matrix $U$ is a product of two involutions, in which case the spectrum of the walk is under control. We construct a new walk that fits in the same framework, from an orientable embedding of a graph. On one hand, this walk is closely connected to the coined walk that has been extensively studied; on the other hand, it enjoys some properties that other models do not exhibit. We will look at interesting walks from special embeddings, and prove some results through spectral analysis.
