Algebraic Graph Theory Seminar: Mondays 11:30 Waterloo, ON time
Upcoming talks
Affiliation: Stanford University, United States
Title: Squares of eigenvalues and semi-definite optimization
Abstract: I will share some recent progress on two long-standing conjectures in spectral graph theory, namely the Elphick-Farber-Goldberg-Wocjan conjecture and the Bollobás-Nikiforov conjecture. Both conjectures involve bounds on the sum of squares of the eigenvalues of a graph, and a key ingredient in our work is the interpretation of such sums as optimization problems involving semi-definite matrices. Part of the talk is joint work with Gabriel Coutinho and Thomás Jung Spier.
Past talks
Abstract:
We study simplicial complexes (hypergraphs closed under taking subsets) that are the intersection of a given number k of matroids. We prove bounds on their chromatic numbers (the minimum number of edges required to cover the ground set) and their list chromatic numbers. Settling a conjecture of Kiraly and Berczi--Schwarcz--Yamaguchi, we prove that the list chromatic number is at most k times the chromatic number. The tools used are in part topological.
If time permits, I will also discuss a result proving that the list chromatic number of the intersection of two matroids is at most the sum of the chromatic numbers of each matroid, improving a result by Aharoni and Berger from 2006.
The talk is based on works joint with Ron Aharoni, Eli Berger, and Daniel Kotlar.
In this talk, there is no assumption about background knowledge of matroid theory or algebraic topology.
Abstract:
Abstract: Graphs and their noncommutative analogues are interesting objects of study from the perspectives of operator algebras, quantum information and category theory. In this talk we will introduce equivariant graphs with respect to a quantum symmetry along with examples such as classical graphs, Cayley graphs of finite groupoids, and their quantum analogues. We will also see these graphs can be constructed concretely by modeling a quantum vertex set by an inclusion of operator algebras and the quantum edge set by an equivariant endomorphism that is an idempotent with respect to convolution/Schur product. Equipped with this viewpoint and tools from subfactor theory, we will see how to obtain all these idempotents using higher relative commutants and the quantum Fourier transform. Finally, we will state a quantum version of Frucht's Theorem, showing that every quasitriangular finite quantum groupoid arises as certain automorphisms of some categorified graph.
Abstract:
Let A (D) denote the adjacency (distance) matrix of a graph G with n vertices. We define the k-th determinantal ideal of MX := diag(x1, x2, …, xn) + M as the ideal generated by all of its minors of size k ≤ n. If M = A, we call this the k-th critical ideals of G. On the other hand, if M = D, we call it the k-th distance ideals of G. These algebraic objects are related to the spectrum of their corresponding graph matrices, their Smith normal form, and in consequence to their sandpile group, for instance. In this talk, we will explore some of the properties and applications of these ideals.
Abstract:
I will present some old constructions of cospectral graphs, due Brendan McKay and myself. I will also describe how we found some of these.
In the talk, I will show how Lasoń’s generalization of Alon’s Combinatorial Nullstellensatz can be used to obtain lower bounds on Turán numbers of complete r-partite r-uniform hypergraphs. As an example, I will give a short and simple explicit construction of a hypergraph free of copies of the complete r-partite r-uniform hypergraph with parts of size 2, thereby providing a lower bound for the so-called Erdős box problem. This asymptotically matches best known bounds when r ≤ 4.
In this talk, we investigate the multiplicative structure of a shifted multiplicative subgroup and its connections with additive combinatorics and the theory of Diophantine tuples and Diophantine graphs. First, we show that if a nontrivial shift of a multiplicative subgroup G contains a product set AB, then |A||B| is essentially bounded by |G|, refining a well-known consequence of a classical result by Vinogradov. Second, we provide a sharper upper bound of Mk(n), or the clique number of Diophantine graphs, which is the largest size of a set such that each pairwise product of its elements is n less than a k-th power, refining the recent result of Dixit, Kim, and Murty. One main ingredient in our proof is the first non-trivial upper bound on the maximum size of a generalized Diophantine tuple over a finite field. In addition, we determine the maximum size of an infinite family of generalized Diophantine tuples over finite fields with square order, which is of independent interest.
We also present a significant progress towards a conjecture of Sárközy on the multiplicative decompositions of shifted multiplicative subgroups. In particular, we prove that for almost all primes p, the set {x2-1: x ∈ Fp*} ∖ {0} cannot be decomposed as the product of two sets in Fp non-trivially.
Abstract:
I will describe nine of my conjectures in spectral graph theory, four of which have been proved to date. The conjectures include lower bounds for chromatic numbers and the clique number and a Nordhaus-Gaddum bound.
Two of the conjectures concern lower bounds for the square energies of graphs, which are the sums of squares of the positive and negative eigenvalues of the adjacency matrix of a graph. One of these conjectures was placed 1st in a wide-ranging survey of unsolved problems in spectral graph theory published last year.
I will conclude with an unpublished potential new approach to these conjectures on square energies, which involves a 1940 result due to Coulson.
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.
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 Bi. 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 Bi 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 Kk,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 BCBT, 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 = BCBT. 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 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.
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.
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
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.
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 c2 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 wT (called the stationary distribution for T) whose entries sum to 1 such that the powers of T converge to the outer product of wT 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.