Algebraic Graph Theory Seminar: Mondays 11:30 Waterloo, ON time
Upcoming talks
Affiliation: Tohoku University, Japan
Title: Abelian covers of association schemes with applications to SIC-POVM
Abstract:
Godsil and Hensel (1992) developed a theory of abelian covers of complete graphs to construct antipodal distance-regular graphs of diameter 3. More recently, Coutinho, Godsil, Shirazi and Zhan (2016) showed that equiangular tight frames can be constructed from covers of complete graphs in terms of cyclic groups of prime order. In this talk, we introduce covers of (not necessarily symmetric) association scheme of d classes in terms of an (not necessarily cyclic) abelian group G of order d. As applications, we show that amorphic pseudocyclic association schemes of class 2k on n vertices can be used to construct distance-regular antipodal 2k-covers of the complete graph with n+1 vertices, by taking G to be the elementary abelian group of order 2k. We also show that a fissioned generalized hexagon of order (2,2) can be used to construct a 7-class association scheme on 256 points, by taking G to be the cyclic group of order 4. This scheme represents 64 lines in the complex 8-dimensional space, forming a SIC-POVM. This talk is based on joint work with Jesse Lansdown.
Past talks
Abstract:
In this talk, we'll explore several new constructions of strongly regular graphs. Specifically, we will show how some known optimal line packings can be coerced into generating new families of SRGs. We will also introduce a new construction of optimal line packings, yielding additional infinite families of SRGs.
Abstract:
A vertex-face walk is a type of discrete-time quantum walk on the arcs of an orientable map (i.e. a 2-cell embedding of a graph on an orientable surface). This walk was introduced by Zhan (2021). If the walk starts in a uniform superposition of the arcs coming out of a vertex u, and ends up in a superposition of arcs coming out of a vertex v after some time t, we say that there is perfect state transfer (PST) at that time t. If u = v, we say that there is periodicity at v at time t. It has turned out to be a challenge to come up with examples of maps that admit PST and periodicity. We show how projecting the walk down onto the vertex space results in a sequence of matrices that satisfy a Chebyshev recursion. This will give us a necessary condition for periodicity to occur.
This Chebyshev recursion can be used to show that periodicity can occur at any time in a certain family of toroidal grids. We also show that periodicity does not occur outside this family (and hence no PST can occur either). Most other cases can be ruled out from admitting periodicity by considering the characteristic polynomial of the transition matrix. The remaining cases are dealt with by applying a theorem from a paper by Conway and Jones, on equations involving roots of unity.
This is joint work with Krystal Guo.
Abstract:
The positive discrepancy of a graph G of edge density p is defined as the maximum of e(U) - p|U|(|U|-1)/2, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is d-regular graph on n vertices and d = O(n1/9), then the positive discrepancy of G is at least c*d1/2n for some constant c. We extend this result by proving lower bounds for the positive discrepancy with average degree d when d < (1/2 - ε)*n. We prove that the same lower bound remains true when d < n2/3, while in the ranges n2/3 < d < n4/5 and n4/5 < d < (1/2 - ε)*n we prove that the positive discrepancy is at least n2/d and d1/4n/log(n) respectively. Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when d < n3/4, thus demonstrating a change in the behavior around d = n2/3 when a random graph no longer minimizes the positive discrepancy. As a by-product, we also present lower bounds for the second largest eigenvalue of a d-regular graph when d < (1/2 - ε)n, thus extending the celebrated Alon-Boppana theorem. This is joint work with Benjamin Sudakov and István Tomon.
Abstract:
Over the past 30 or so years, the realization that graphs can be viewed as discrete analogues of Riemann surfaces has led to a fruitful interplay between algebraic geometry, tropical geometry, and graph theory. Among other things, this has led to the study of new graph parameters, including various notions of the gonality of a graph. In addition to its ties with algebraic and tropical geometry, graph gonality also turns out to have connections with chip-firing games, structural graph theory, and parametrized complexity. In this talk, I will introduce the two most common types of graph gonality (namely, divisorial gonality and stable gonality) and survey the most important results and open problems in this field, including the connections with the aforementioned topics.
Abstract:
In this talk I will fist introduce Riis' guessing game and how it relates to various graph parameters, including the minrank of a graph. Next I will discuss some ongoing work with Demetres Christofides on how to construct semi-random graphs with low minrank.
Abstract:
Spectral graph theory provides us with a wide array of surprising results which relate graph-theoretic parameters to linear-algebraic parameters of associated matrices. Among the most well-known and useful of these is Hoffman’s ratio bound, which gives an upper bound on the independence number of a graph in terms of its eigenvalues.
A closely related result is Cvetković’s inertia bound, another inequality relating the independence number and the eigenvalues of a graph. Despite its similarity to the ratio bound, the inertia bound is much less well-understood—until a few years ago, it was unknown whether this simple inequality is always an equality! In this talk, I will survey what is known about these two bounds, and will present a powerful new approach to answering such questions.
Joint work with Matthew Kwan.
Abstract:
For a distance-regular graph X and an arbitrary vertex v, we often find interesting structure in the subgraph of X induced on vertices at distance 2 from v. For example:
Any strongly-regular graph with parameters (n,k,a,k/2) can be found at distance 2 from a vertex in a distance-regular graph of diameter 3.
Certain distance-regular graphs of diameter 3 can be found at distance 2 from a vertex in a Moore graph of girth 5.
These (and more) examples are known as second-subconstituents, and they can be studied using the Terwilliger (or subconstituent) algebra of X. I will discuss this theory in the case that X is a distance-regular antipodal cover of a complete graph (drackn). This setting generalizes the first example and includes the second.
I will describe some general techniques for studying the Terwilliger algebras of drackns and then restrict to drackns without triangles. In this setting I will explain how to compute the spectrum of the second-subconstituent of any triangle-free drackn, except possibly the second-subconstituent OF a second-subconstituent of a Moore graph of valency 57.
Abstract:
Abstract: Let X be a graph and let E1, ..., Ed be the spectral idempotents of its adjacency matrix. If a and b are vertices in X, they are strongly cospectral if Er eaeaT Er = Er ebebT for each r. This is a relation between the two density matrices eaeaT and ebebT, and is a necessary condition for state transfer between pure states.
If L is the Laplacian of a graph X with m edges, the matrix (1/2m)L is positive semidefinite with trace one, thus it is a density matrix. We call it a Laplacian state. It is pure only if X is an edge. We have been investigating transfer between Laplacian states in continuous quantum walks. We have extended the definition of strongly cospectral to this case, have obtained a number of results about various forms of state transfer. My talk will be a report on this.
(This is joint work with Ada Chan, Qiuting Chen, Wanting Sun, and Xiaohong Zhang.)
Abstract:
In this talk, we introduce the notion of vertex sedentariness. We discuss a necessary condition for vertex sedentariness and provide infinite families of graphs with sedentary vertices. It turns out, vertex sedentariness and pretty good state transfer are mutually exclusive types of quantum state transfer. There are infinite families of graphs with vertices that are neither sedentary nor involved in pretty good state transfer (PGST). But for the case of twin vertices, it is a dichotomy: a vertex with a twin is either sedentary or is involved in PGST. We also show that strongly cospectral vertices can be sedentary, despite the fact that this property is required for PGST. Constructions that preserve and induce vertex sedentariness will also be presented. We conclude with some open questions, if time permits. This talk is based on the following preprints: Sedentariness in quantum walks and New results in vertex sedentariness.
I will discuss the notion of PGFR relative to a given subset of nodes of a graph. This is a generalization of the more standard (pretty good) fractional revival between 2 nodes. In the process, I will introduce the proper generalization of cospectrality to the fractional setting, and give the appropriate extensions of methods already in use for the 2-vertex case. These include the Kronecker condition and the field-trace method. I will conclude by giving various families of examples of PGFR in the presence of (transcendental) magnetic fields.
A non-backtracking walk in a graph is any traversal of the vertices of a graph such that no edge is immediately repeated. The non-backtracking matrix of a graph is indexed by the directed edges of the graph, and encodes if two edges can be traversed in succession. Since this matrix is not symmetric, the question of when the matrix is diagonalizable is of interest to those who study it. Equivalently, such graphs have a non-trivial Jordan block. In this talk, I will present an overview of the non-backtracking matrix, including its history and applications. Finally, I will present recent results about graphs with non-trivial Jordan blocks for the non-backtracking matrix from joint work with Kristin Heysse, Kate Lorenzen, and Xinyu Wu.
Abstract:
A simplicial complex is a topological space built by gluing together simple building blocks (such as vertices, edges, triangles and their higher dimensional counterparts). Alternatively, we can define a simplicial complex combinatorially, as a family of finite sets that is closed under inclusion. In 1944, Eckmann introduced a class of high dimensional Laplacian operators acting on a simplicial complex. These operators generalize the Laplacian matrix of a graph (which can be seen as a 0-dimensional Laplacian), and are strongly related to the topology of the complex (and in particular, to its homology groups).
In this talk, I will show different ways in which one can obtain information on the spectrum of a high dimensional Laplacian operator on a simplicial complex from the spectra of its lower dimensional Laplacians, and present several applications to the study of the topology of the complex. In addition, I will discuss one of our main technical tools, the use of "additive compound matrices" for studying sums of eigenvalues of a linear operator, which may be of independent interest.
The construction and analysis of Hadamard matrices have been a long-standing problem in combinatorial design theory. Recently, Kharaghani and Suda introduced balanced splittable Hadamard matrices, a special type of Hadamard matrices with intriguing internal structures. These matrices have natural connections to various combinatorial objects, especially strongly regular graphs.
By incorporating the notion of primitive/imprimitive strong regular graphs into balanced splittable Hadamard matrices, we classify balanced splittable Hadamard matrices into five classes whose parameters are determined. We describe a simple but powerful construction of balanced splittable Hadamard matrices using elementary abelian 2-groups.
The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells. The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once. We can extend Sudoku so that the boxes are h-by-w, and the overall array is n-by-n, where n=hw. The puzzle is now similar to completing a Latin square of order n, except, of course, that Sudoku has an additional box condition.
Through studying a system of linear equations associated with Sudoku Latin squares, we encounter some interesting eigenvalues and eigenvectors. These can be used (with the help of a computer) to show that every sufficiently large and sparse Sudoku puzzle has a fractional solution. This fractional relaxation permits the player to cut up their symbol allocations into positive fractional pieces, so long as every entry still receives one symbol worth of allocation, and every row, column, and box still has every symbol occurring exactly once.
This is joint work with my MSc student Kate Nimegeers.
Given a finite transitive group G ≤ Sym(Ω), a subset 𝓕 ⊆ G is intersecting if any two elements of 𝓕 agree on some elements of Ω. The intersection density of G is the rational number ρ(G) given by the maximum ratio |𝓕| / (|G| / |Ω|), where 𝓕 runs through all intersecting sets of G.
Most results on the intersection density focus on particular families of transitive groups. One can look at problems on the intersection density from another perspective. Given an integer n ≥ 3, we would like to determine the possible intersection densities of transitive groups of degree n. This problem turns out to be extremely difficult even in the case where n is a product of two primes.
In 2022, Meagher asked whether ρ(G) ∈ {1, 3/2, 3} for any transitive group G ≤ Sym(Ω) of degree |Ω| = 3p, where p ≥ 5 is an odd prime.
In this talk, I will present some recent progress on this question. I will also talk about more general results in the case where n is a product of two distinct odd primes.
Abstract:We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum version of Jordan’s theorem for the automorphism groups of trees. This is one of the first characterisations of quantum automorphism groups of a natural class of graphs with quantum symmetry. This talk is based on the following preprint: https://arxiv.org/abs/2311.04891
Abstract:
Given a connected bipartite graph G, the adjacency matrix A of G can be decomposed as A=L+R, where L=L(x) and R=R(x) are respectively the lowering and the raising matrices with respect to a certain vertex x. The graph G has a uniform structure with respect to x if the matrices RL2, LRL, L2R, and L satisfy a certain linear dependency.
Let Γ=(X,E) be a connected non-bipartite graph. Fix a vertex x ∈ X and let Γf=(X,Ef) be the bipartite graph, where Ef=E \ {yz | ∂(x,y) = ∂(x,z)} and ∂ is the distance function in Γ. The graph Γ is said to support a uniform structure whenever Γf has a uniform structure with respect to x.
In this talk, I will present some classification results of non-bipartite distance-regular graphs with classical parameters (D,q,α,β), that support a uniform structure.
Joint work with: Blas Fernández, Štefko Miklavič, and Giusy Monzillo.
Abstract: Kemeny's constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are. This comes to the forefront when the Markov chain in question is a random walk on a graph, in which case Kemeny's constant is interpreted as a measure of how `well-connected' the graph is. Though it was first introduced in the 1960s, interest in this concept has recently exploded. This talk will provide an introduction to Markov chains, an overview of the history of Kemeny’s constant, discussion of some applications, and a survey of recent results, with an emphasis on those that are extensions or generalizations of simple random walks on graphs, to complement Sooyeong’s talk from two weeks ago.
Abstract: Given a simple graph G=(\{1,\ldots, n},E), we consider the class S(G) of real symmetric n \times n matrices A=[a_{ij}] such that for i\neq j, a_{ij}\neq 0 iff ij \in E. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), q(G) - known as the minimum number of distinct eigenvalues of G - has emerged as one of the most well-studied parameters of the IEPG. Naturally, characterizing graphs G for which q(G) \leq, =, \geq k is an important step for studying the IEPG. A tantalizing (and maddened) puzzle is to characterize the graphs G with q(G)=2. Equivalently, such graphs are precisely the graphs for which S(G) admits an orthogonal matrix. In this talk I intend to discuss the continuing saga of attempting to learn more about the graphs G with q(G)=2...
Abstract: In the r-bond bootstrap percolation process on a graph G, we start with a set of initially infected edges of G and consider all other edges to be healthy. At each step in the process, a healthy edge is infected if at least one of its endpoints is incident with at least r infected edges. In this process, infected edges will remain infected indefinitely. A set of initially infected edges that will eventually infect every edge in G is known as an r-percolating set of G.
We are interested in determining the minimum number of edges in an r-percolating set of G, denoted by m_e(G,r). Recently, Hambardzumyan, Hatami, and Qian introduced a clever polynomial method for finding lower bounds on m_e(G,r), which they used to provide recursive formulas for m_e(G,r) when G is either a d-dimensional torus or a d-dimensional grid. In this talk, we will investigate their polynomial method, and see how it can be applied to provide recursive formulas for m_e(G,r) when G is a product of certain other graphs H. Based on work with Natasha Morrison.
Abstract: Kemeny's constant, a fundamental parameter in the theory of Markov chains, has recently received significant attention within the graph theory community. Originally defined for a discrete, finite, time-homogeneous, and irreducible Markov chain based on its stationary vector and mean first passage times, Kemeny's constant finds special relevance in the study of random walks on graphs. Kemeny's constant gives a measure of how quickly a random walker can move around a graph, and is thus a good measure of the connectivity of a graph. It is natural to study how graph structure informs a graph invariant. In this talk, we will understand how graph structures provide insights into Kemeny’s constant. In addition, we will also examine how the addition of an edge affects Kemeny’s constant.
Abstract: A Neumaier graph is an edge-regular graph with a regular clique. Several families of strongly regular graphs (but not all of them) are indeed Neumaier, but in 1981 it was asked whether there are Neumaier graphs that are not strongly regular. This question was only solved a few years ago by Greaves and Koolen, so now we know there are so-called strictly Neumaier graphs.
In this talk I will discuss several new results on (strictly) Neumaier graphs, including bounds on the parameters and (non)-existence results obtained in various ways. I will focus on a new construction (involving Cayley graphs) producing an infinite number of strictly Neumaier graphs, but I will also discuss a new Neumaier graph arising from a Latin square. This talk is based on joint research with A. Abiad, W. Castryck, J.H. Koolen and S. Zeijlemaker.
Abstract: The main purpose of this talk is to explain the idea behind the main results of a recent article arXiv:2210.02047 about quantum symmetries of Hadamard matrices. First, we recall the notion of quantum symmetries from the viewpoint of quantum groups as well as diagrammatic categories. On the example of a finite (quantum) space, we show, how the diagrammatic approach can be used to prove that all finite spaces (of size at least four) have quantum symmetries and all finite quantum spaces of a given size are mutually quantum isomorphic. The same technique is used to show analogous results for Hadamard matrices. Finally, we would like to list a couple of questions and research suggestions related to this topic.
Abstract: If H is a Hermitian matrix, then the matrices U(t)=exp(itH) determine a quantum walk. (Usually H will be some type of weighted adjacency matrix). A complex matrix is flat if its entries all have the same absolute value. A quantum walk admits uniform mixing if there is a time t such that U(t) is flat. The usual walk on the hypercube admits uniform mixing. If a unitary matrix is flat, then it is a scalar multiple of a complex Hadamard matrix.
A walk admits local uniform mixing relative to an initial state with density matrix D if there is a time t such that the diagonal entries of U(t)DU(-t) are all equal.If we have local uniform mixing at time t from each vertex state e_ae_a^T, then we have uniform mixing.
The basic question is to decide which graphs admit uniform mixing or local uniform mixing. I will summarise some of the work by Mullin, Zhan and Chan, and some more recent work with Xiaohong Zhang.
Abstract: In 1990, Vaughn Jones introduced a link invariant constructed using matrices known as spin models. In 1996, Francois Jaeger discovered that spin model matrices are contained in the Bose-Mesner algebra of an association scheme. Since many examples of association schemes arise from distance-regular graphs, it is natural to ask which distance-regular graphs afford a spin model. Several known families exist, and it is conjectured that the known list is complete. In this talk we present results describing the Terwilliger algebra of a distance-regular graph Γ that affords a spin model. We use the results to restrict the possible parameters of Γ. In future work, we expect that such restrictions could lead to a classification of the distance-regular graphs that afford a spin model.
Abstract: The sandpile group K(G) of a graph G is a finite abelian group, isomorphic to the cokernel of the reduced graph Laplacian of G. We study K(G) when G = Cone(T) is obtained from a tree T on n vertices by attaching a new cone vertex attached to all other vertices. For two such families of graphs, we will describe K(G) exactly: the fan graphs Cone(P_n) where P_n is a path, and the thagomizer graph Cone(S_n) where S_n is the star-shaped tree. The motivation is that these two families turn out to be extreme cases among Cone(T) for all trees T on n vertices.
Abstract:
We say two graphs X and Y with respective adjacency matrices A and B are fractionally isomorphic if there is a doubly stochastic matrix S such that AS=SB. We refer to S as a fractional isomorphism; if Y=X, then S is a fractional automorphism. Since permutation matrices are doubly stochastic, the permutation matrices belonging to automorphisms of X lie in S(X). The set S(X) of all fractional isomorphisms of X is a convex polytope and the permutation matrices in S(X) are vertices of this polytope. Tinhofer defined a graph to be compact if all vertices of S(X) are permutations.
I will discuss some of the theory of fractional isomorphisms and compact graphs. I will also discuss an interesting map from quantum automorphisms of X into S(X).
Abstract:
Splines are defined as piecewise polynomials on the faces of a polyhedral complex that agree on the intersections of two faces. Splines are used in approximation theory and numerical analysis, with applications in data interpolation, to create smooth curves in computer graphics and to find numerical solutions to partial differential equations. Gilbert, Tymoczko, and Viel generalized the classical splines combinatorially and algebraically: a generalized spline is a vertex labeling of a graph G by elements of the ring so that the difference between the labels of any two adjacent vertices lies in the ideal generated by the
corresponding edge label. We study the generalized splines on the planar graphs whose edges are labeled by two-variable polynomials of the form (ax+by)^2.