Algebraic Graph Theory Seminar: Mondays 11:30 Waterloo, ON time

Upcoming talks

Affiliation: The University of Western Australia - Australia

Title: Ramsey numbers and configurations of finite polar spaces

Abstract: This talk is on some joint work with Anurag Bishnoi and Ferdinand Ihringer, about a simple observation on how Ramsey theory relates to certain induced subgraphs of collinearity graphs arising from finite polar spaces; the natural geometries for the finite simple groups of classical Lie type.

Past talks

Abstract:

In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs.

Orthogonal polynomials emerging in the context of P- and Q-polynomial association schemes are known to reside within the Askey-scheme. This relationship forms a bridge between algebraic combinatorics and the study of special functions, yielding significant benefits for both fields. Recent research has introduced multivariate generalizations of P- and Q-polynomial association schemes and provided numerous examples. This development aims notably to deepen our understanding of multivariate analogues of Askey-Wilson polynomials. In this talk, we will review this generalization, its connection to m-distance-regular graphs, and an algebraic combinatorial structure known as a "uniform poset," from which many examples of bivariate schemes appear to originate.

Abstract:

An equiangular tight frame is a special kind of matrix, and when it exists, its columns represent an arrangement of lines through the origin that maximizes the minimum interior angle. In this talk, we pose the "d-by-2d conjecture": there exists a d-by-2d equiangular tight frame for every dimension d. We also construct two new infinite families of such equiangular tight frames, we identify a third construction that conjecturally applies for all d, and we show that the conjecture holds whenever d is at most 162. Based on joint work with Joseph Iverson and John Jasper.

In [Proc. Amer. Math. Soc. 152, 3, p. 1265] we proved a conjecture of Kresch & Tamvakis from 2001 about a certain _{4F3} hypergeometric series. In this talk, we discuss our proof of the conjecture and a related finding. Specifically, we construct a Leonard pair A, A^{*} and a related sequence of matrices B_{i}. We identify the hypergeometric series in question with the eigenvalues of these matrices. We use the Biedenharn-Elliott identity to prove that the entries of the B_{i} are nonnegative. From this, we discuss two different arguments to derive the conjectured bound: one using the Perron-Frobenius theorem, and another using the theory of spin Leonard pairs.

Abstract:

In this work, we introduce the notion of power lattices, which are a more general class of ranked lattices with additional properties. Then we generalize the concept of shellable simplicial complexes in the lattice of subsets to P-shellable P-complexes in a power lattice P. We show that when the P-complex is P-shellable, its order complex is a shellable simplicial complex. We demonstrate that these P-complexes can be constructed by generalizing the concept of matroids to matroids in a power lattice P. This provides various constructions of posets with desirable topological and algebraic properties. In the particular class of lattices of multiset subsets, we show how to construct shellable 'multicomplexes' from weighted graphs. Finally, we illustrate how shellable multicomplexes give rise to rings that are sequentially Cohen-Macaulay.

Abstract:

A web is a directed, labeled plane graph satisfying certain conditions coming from representation theory. Each web corresponds to a specific invariant vector in a tensor product of fundamental representations of a quantum group. In this talk, we introduce a process called stranding, which encodes as the monomial terms in a web's associated vector as a collection of paths in the web graph. We also describe how the strandings connect seemingly-unrelated ideas in combinatorics (e.g. noncrossing matchings) and geometry (e.g. certain algebraic varieties called Springer fibers).

Abstract:

The extremal graphs EX(n, 𝔼) and spectral extremal graphs SPEX(n, 𝔼) are the sets of graphs on n vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in 𝔼. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families 𝔼 and implies several new and existing results. In particular, whenever EX(n, 𝔼) contains the complete bipartite graph K_{k,n-k} (or certain similar graphs) then SPEX(n, 𝔼) contains the same graph when n is sufficiently large. We prove a similar theorem which relates SPEX(n, 𝔼) and SPEX_{α}(n, 𝔼), the set of 𝔼-free graphs which maximize the spectral radius of the matrix A_{α} = α D + (1 - α) A, where A is the adjacency matrix and D is the diagonal degree matrix.

Walks and closed-walks are ubiquitous in graph theory, which capture lots of important structural information of graphs. In this talk, we shall consider the question in the title. The same question for closed walks is precisely the problem of spectral characterizations of graphs. We show that for most graphs, the number of walks determines the generalized spectrum of graphs and vice versa. Then the above question is equivalent to the problem of generalized spectral characterizations of graphs, a topic which has been studied extensively in recent years. Some simple criterions are provided for graphs G to be determined by their total number of walks, based on some recent results on the generalized spectral characterizations of graphs. Numerical results are also provided to illustrate the effectiveness of the proposed method. This is a joint work with Weifang Lv, Finjin Liu and Wei Wang.

Abstract:

Factorizations of matrices where the factors are required to be entry-wise nonnegative provide a powerful tool in analyzing nonnegative data. In this talk we will consider Symmetric Nonnegative Matrix Trifactorization (SN-Trifactorization), a factorization of nonnegative symmetric matrices that takes into account symmetry, non-negativity, and low rank of a matrix.

SN-Trifactorization is a factorization of an n × n (entry-wise) nonnegative symmetric matrix A of the form BCB^{T}, where C is a k × k symmetric matrix, and both B and C are required to be nonnegative. The SNT-rank of A is the minimal k for which such factorization exists. The zero-nonzero pattern of A poses constraints on the zero-nonzero pattern of B and C satisfying A = BCB^{T}. Those constraints can be studied through the SNT-rank of simple graphs that allow loops, defined to be the minimal possible SNT-rank of all symmetric nonnegative matrices whose zero-nonzero pattern is prescribed by a given graph.

After introducing the SNT-rank of nonnegative symmetric matrices and exploring its basic properties, we will turn our discussion to the SNT-rank of graphs. We will define set-join covers of graphs and show that finding the SNT-rank of a graph G is equivalent to finding the minimal order of a set-join cover of G. Using this insight, we will develop basic properties of the SNT-rank for graphs and compute it for trees and cycles without loops. We will show the equivalence between the SNT-rank for complete graphs and the Katona problem and discuss the uniqueness of patterns of matrices in the factorization.

Two graphs are called quantum isomorphic if they have the same homomorphism counts from all planar graphs. In this talk, we discuss the construction of a pair of quantum isomorphic, non-isomorphic strongly regular graphs. The pair consists of the orthogonality graph of the 120 lines spanned by the E8 root system and a rank 4 graph whose complement was first discovered by Brouwer, Ivanov and Klin. Both graphs are strongly regular with parameters (120, 63, 30, 36). We will see that one can obtain more quantum isomorphic, non-isomorphic strongly regular graphs using Godsil-McKay switching.

A k-regular graph on v vertices is called a Deza graph with parameters (v, k, b, a), b ≥ a if the number of common neighbors of any two distinct vertices takes two values: a or b. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular.
In this talk we will discuss the enumeration of strictly Deza graphs and the enumeration of special subclass of strictly Deza graphs called divisible design graphs. We will also describe the constructions of divisible design graphs found during the enumeration.
In the second part of talk we discuss the vertex connectivity of strictly Deza graphs and divisible design graphs. We will look at the cases with vertex connectivity less than k, where k is the regularity of the graph. In particular, we will show that the vertex connectivity of strictly Deza graphs can be less than k by any amount.

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 2^{k} on n vertices can be used to construct distance-regular antipodal 2^{k}-covers of the complete graph with n+1 vertices, by taking G to be the elementary abelian group of order 2^{k}. 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.

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(n^{1/9}), then the positive discrepancy of G is at least c*d^{1/2}n 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 < n^{2/3}, while in the ranges n^{2/3} < d < n^{4/5} and n^{4/5} < d < (1/2 - ε)*n we prove that the positive discrepancy is at least n^{2}/d and d^{1/4}n/log(n) respectively. Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when d < n^{3/4}, thus demonstrating a change in the behavior around d = n^{2/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 E_{1}, ..., E_{d} be the spectral idempotents of its adjacency matrix. If a and b are vertices in X, they are strongly cospectral if E_{r} e_{a}e_{a}^{T} E_{r} = E_{r} e_{b}e_{b}^{T} for each r. This is a relation between the two density matrices e_{a}e_{a}^{T} and e_{b}e_{b}^{T}, 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

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 RL^{2}, LRL, L^{2}R, 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,E_{f}) be the bipartite graph, where E_{f}=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.

Problem. When the Bose–Mesner algebra 𝒜 of commutative d-class association scheme 𝔘 (which is not necessarily symmetric) can be generated by a 01-matrix A? In other words, for a given 𝔘, can we find a 01-matrix A such that 𝒜 = (⟨ A ⟩, +, ·)? Moreover, since such a matrix A is the adjacency matrix of some (un)directed graph 𝛇, can we describe the combinatorial structure of 𝛇? The vice-versa question is also of importance, i.e., what combinatorial structure does the (un)directed graph need to have so that its adjacency matrix will generate the Bose–Mesner algebra of a commutative d-class association scheme 𝔘?

Abstract:

Rank 3 graphs are graphs whose full automorphism group acts as a rank 3 group on the vertices. Finite rank 3 groups are classified and hence finite rank 3 graphs are classified. The main examples arise from geometric structures such as projective and polar spaces, and there is one class of examples related to the exceptional groups of type E6. We present a combinatorial/geometric/projective construction of these graphs. We then consider a class of regular sets, that is, subsets S of the vertices such that the number of vertices of S adjacent to some vertex v only depends on whether v belongs to S or not. We will explain how this leads to characterizations of certain automorphisms of the E6 graphs and other graphs.

Abstract:

In 1995, Lazebnik and Ustimenko introduced the family of q-regular graphs D(k, q), which is defined for any positive integer k and prime power q. The connected components of the graph D(k, q) have provided the best-known general lower bound on the size of a graph for any given order and girth to this day. Furthermore, Ustimenko conjectured that the second largest eigenvalue of D(k, q) is always less than or equal to 2√q, indicating that the graphs D(k, q) are good expanders. In this talk, we will discuss some recent progress on this conjecture. This includes the result that the second largest eigenvalue of D(5, q) is less than or equal to 2√q when q is an odd prime power. This is joint work with Vladislav Taranchuk.

In the survey paper by Van Dam, Koolen, and Tanaka (Distance-regular graphs, Electron. J. Comb., Dynamic Survey (2016), #DS22), they asked to classify the thin Q-polynomial distance-regular graphs. In this talk, we will discuss our result which states that the Grassmann graphs with large diameter are characterized by their intersection numbers under the extra condition that they are thin.

This is joint work with Jack Koolen and Ying-Ying Tan.

I have for many years been interested in graph invariants with the same symmetries as the Feynman period. Recently Erik Panzer found a new such invariant coming from a particular coefficient of the Martin polynomial. Together we used this to prove an over 10 year old conjecture on an arithmetic graph invariant known as the c_{2} invariant, and came to understand that diagonal coefficients of Kirchhoff polynomials tie together many of the known graph invariants with the symmetries of Feynman periods and unlock previously inaccessible proofs.
Joint work with Erik Panzer.

A partial geometric design with parameters (v, b, k, r; α, β) is a tactical configuration (P, B) (with |P|=v, |B|=b, every point p ∈ P belonging to r blocks, and every block B ∈B consisting of k points) satisfying the property:

For any pair (p, B) ∈ P × B, the number of flags (q, C) with q ∈ B and C ∋ p equals to α if p ∉ B and to β if p ∈ B.

Neumaier studied partial geometric designs in detail in his article, “t1/2-designs,” [JCT A 28, 226-248 (1980)]. He investigated their connection with strongly-regular graphs and gave various characterizations of partial geometries, bipartite graphs, symmetric 2-designs, and transversal designs in terms of partial geometric designs.

In this talk, we review a few recent works on partial geometric designs and the related topics, and discuss the concurrence profiles of pairs of points together with the incidence relations between points and blocks of the designs. Through the analysis of their concurrence matrices, we give further characterization of partial geometric designs. We also investigate their connection with directed strongly-regular graphs and association schemes (and other finite incidence structures if time permits). This talk is a survey expository on the topics.

For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.
Slides

Abstract:

We investigate state transfer on a hypercube by means of a quantum walk where the sender and the receiver vertices are marked by weighted loops. First, we analyze search for a single marked vertex, which can be used for state transfer between arbitrary vertices by switching the weighted loop from the sender to the receiver after one run-time. Next, state transfer between antipodal vertices is considered. We show that one can tune the weight of the loop to achieve state transfer with high fidelity in shorter run-time in comparison to the state transfer with a switch. Finally, we investigate state transfer between vertices of arbitrary distance. It is shown that when the distance between the sender and the receiver is at least 2, the results derived for the antipodes are well applicable. If the sender and the receiver are direct neighbours the evolution follows a slightly different course. Nevertheless, state transfer with high fidelity is achieved in the same run-time. The talk is based on joint results with Stanislav Skoupy.

A square nonnegative matrix T is called stochastic if all of its row sums are equal to 1. Under mild conditions, it turns out that there is a positive row vector w^{T} (called the stationary distribution for T) whose entries sum to 1 such that the powers of T converge to the outer product of w^{T} with the all-ones vector. Further, the nature of that convergence is governed by the eigenvalues of T.

In this talk, we explore how the stationary distribution for a stochastic matrix exerts an influence on the corresponding eigenvalues. We do so by considering the region in the complex plane comprised of all eigenvalues of all stochastic matrices with a given stationary distribution. We establish a few properties of that region, and of the variant that arises by considering the so-called reversible stochastic matrices. For the reversible version of the problem, the graphs associated with the reversible stochastic matrices are a useful tool.

The Johnson and Kneser graphs have the same eigenspaces. How explicitly can we describe these eigenspaces? We describe an explicit orthogonal basis for each eigenspace, which coincides with the Gelfand–Tsetlin basis. We also discuss related work on other graphs, including many open questions.
Joint work with Nathan Lindzey (Technion).

Abstract:

In the recent years self-testing has grown into a rich and active area of study with applications ranging from practical verification of quantum devices to deep complexity theoretic results. Self-testing allows a classical verifier to deduce which quantum measurements and on what state are used, for example, by provers Alice and Bob in a nonlocal game. Hence, self-testing as well as its noise-tolerant cousin, robust self-testing, are desirable features for a nonlocal game to have. Contrary to what one might expect, we have a rather incomplete understanding of if and how self-testing could fail to hold. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Also, is it the case that every self-testing result can be turned robust with enough ingenuity and effort? We answer these questions in the negative by providing simple and fully explicit counterexamples.
This talk is based on a joint work with Simon Schmidt.

Abstract:

Graph classes in the Johnson, Grassmann and Hamming association scheme have received a considerable amount of attention over the last decades. Although several (NP-hard) graph parameters have been investigated for these families, many remain unknown. In this talk, we establish the diameter of generalized Grassmann graphs, extending previous results for generalized Johnson graphs. We also study the zero forcing number of generalized Johnson and Grassmann graphs, as well as Hamming graphs. As a corollary, we obtain the known results for Kneser graphs, Johnson graphs on 2-sets, lattice graphs and hypercubes. This is joint work with Aida Abiad and Robin Simoens.

A cut in a graph G = (V, E) is a set of edges which has one endpoint in S, for a given subset S of V. The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. Beyond its role as part of Šámal's
work on cut continuous functions, this graph parameter also arises as the gauge dual of the maximum cut problem. This connection allows one to extend the celebrated Goemans and Williamson approximation algorithm into this new setting, providing a deeper insight into both. This talk will survey some of the main points of this extension.