05C50 Online

05C50 Online is a biweekly virtual seminar about graphs and matrices held on a Friday, 10AM Central Time via Zoom. This is organized by Stephen Kirkland (University of Manitoba), Hermie Monterde (University of Regina) and Homer de Vera (Univddrsity of Manitoba). Kindly fill out THIS FORM to subscribe to our mailing list!

Jan 9, 10am CT

Speaker: Karen Meagher

Affiliation: University of Regina, Canada

Title: A Gentle Introduction to Erdos-Ko-Rado Combinatorics

Abstract: My research is centred around the famous Erdos-Ko-Rado (EKR) Theorem. I was first introduced to this theorem through an application in computer science, and later learned about its roots in pure mathematics. This is a research area that has grown so much recently that researchers have coined the term "Erdos-Ko-Rado Combinatorics" to describe the field. My talk will be a general introduction to this field, highlighting the different types of problems considered and their connections to different areas of math.

The original EKR Theorem is a problem in extremal set theory; it determines the largest collections of k-subsets from an n-set, with the property that any two of the subsets have non-empty intersection. The collection of all k-subsets that contain a fixed point is clearly an example of such a family (it is called a canonical intersecting family) and the EKR theorem states that it is the largest possible. One reason that the this theorem is so important is that it is a very natural and satisfying result! Further, there are many vastly different proofs of the result, and in recent year many extensions and generalizations have been considered.

One active direction is to show that a theorem analogous to the EKR holds for different objects. So consider any type of object with some notion of intersection, and ask what is the largest collection of objects so that any two from the collection have non-trivial intersection. A natural version of the EKR theorem is known to hold for set partitions, permutations, integer sequences, trees in a graph and many different geometries, just to name a few examples. A common proof method is to define a graph with the property that intersecting sets are exactly the cocliques (also called independent sets) in the graph. Then the problem becomes how to determine the largest cocliques in this graph. With this perspective, tools from linear algebra and algebraic graph theory can be applied and are surprisingly effective. Further, the adjacency matrices of these graphs often belong to a very structured matrix algebra and there can be patterns in the eigenvalues of these association scheme that can be used to find good, and often tight, bounds on the size of the cocliques.

Another direction in EKR combinatorics is to characterize all the largest intersecting sets. Typically, this is a much harder problem, but new and effective methods based on algebraic graph theory have been recently developed. This method considers a collection of Boolean functions defined on a subspace and leads to the study of related sets called Cameron-Liebler sets.

The focus of research has been on objects for which a version of the EKR theorem holds, but some recent work had looked for natural examples where the theorem does not hold. This work has focused on permutation groups, and trying to measure how far the group is to having the EKR theorem hold. There are also some examples where the EKR theorem is conjectured to hold, but the current methods are not effective.

No preprint  |  Recording passcode: 5f8P$f&2  |  Slides

Jan 23, 10am CT

Speaker: Lorenzo Ciardo

Affiliation: TU Graz, Austria

Title: Quantum Polymorphisms

Abstract: A broad class of computational tasks can be phrased as the problem of determining whether two cooperating players, Alice and Bob, can convince a referee that a given statement involving relations between variables is true. Classic examples include colouring the vertices of a graph so that adjacent vertices receive different colours, identifying large independent sets or cliques in a graph, solving systems of linear equations, and finding satisfying assignments to CNF formulas. From this perspective, understanding the complexity of such tasks amounts to analysing how difficult it is for Alice and Bob to devise a winning strategy for the corresponding game.

This viewpoint naturally gives rise to a quantum variant of the problem, in which Alice and Bob are allowed to use shared entanglement to enhance their strategies. In this talk, after a brief introduction to the theory of such games (with no prior knowledge of quantum computing assumed), I will present recent joint work with Gideo Joubert and Antoine Mottet on the complexity of quantum games.

A key insight of this work is that the quantum analogue of an object known as a polymorphism (which has been studied in graph theory and classical complexity theory for decades) precisely characterises when traditional methods for analysing classical games extend to the quantum setting. The main challenge, therefore, is to understand the structure of quantum polymorphisms. Since these objects can ultimately be described as collections of orthogonal projectors satisfying certain geometric conditions, this leads to a purely matrix-theoretic problem, that will be explored in the end of the talk.

Preprint  |  This talk will be recorded  |  You may email the speaker for their slides

Feb 6, 10am CT

Speaker: Carlos Hoppen

Affiliation: Universidade Federal do Rio Grande do Sul (UFRGS), Brazil

Title: Recent progress on the inverse eigenvalue problem

Abstract: The inverse eigenvalue problem has played a central role in spectral graph theory in the last decade. In this talk, I shall be interested in a particular parameter, namely the minimum number of distinct eigenvalues of a graph G, i.e., in the minimum number of distinct eigenvalues of a real symmetric matrix whose underlying graph is G. To be precise, let M be a symmetric matrix of order n. A graph G is said to be the underlying graph of M if its vertex set has n elements and if any pair of distinct vertices i and j are adjacent if and only if the entry ij of M is nonzero. There is no constraint about diagonal entries.

It is well known that, if G is a tree, the value of this parameter is at least d(G)+1, where d(G) is the diameter of G. I will discuss instances where this bound is tight. In a different direction,  I will show that the number of eigenvalues of G is at most 4 whenever G is a cograph, that is, whenever G does not contain an induced path on four vertices.  

This includes joint work with L. Emilio Allem, Martin Fürer, Lucas Siviero Sibemberg, and Vilmar Trevisan.

Preprint 1, 2 and 3  |  This talk will be recorded  |  You may email the speaker for their slides

Feb 20, 10am CT

Speaker: John Urschel

Affiliation: Massachussetts Institute of Technology (MIT), USA

Title: TBA

Abstract: 

Mar 6, 10am CT

Speaker: Veronika Furst

Affiliation: Fort Lewis College (Colorado), USA

Title: The number of edges of graphs that admit two distinct eigenvalues

Abstract: The Inverse Eigenvalue Problem for Graphs (IEP-G) concerns determining all possible spectra of matrices in S(G), the set of real symmetric matrices described by a graph.  Specific subproblems involve studying the maximum nullity or minimum rank, the ordered multiplicity list of distinct eigenvalues, or the minimum number of distinct eigenvalues of a graph.  In this talk, we will share recent results on the last of these, known as the parameter q(G).  In particular, we will investigate bounds on the number of edges of a graph through the “allows problem,” which asks what sparsity allows q(G) = 2, and the complementary “requires problem,” which asks what density requires q(G) = 2.  We will answer the first question, present a characterization of certain regular graphs, and give some evidence in support of a conjectured answer to the second question.

Joint work with W. Barrett, E. Egolf, S. Fallat, F. Kenter, S. Nasserasr, B. Rooney, M. Tait, and H. van der Holst, and partially supported by NSF grant DMS-2331072.

Preprint 1, 2, 3 and 4  |  This talk will NOT be recorded  |  You may email the speaker for their slides

Mar 20, 10am CT

Speaker: JV Morales

Affiliation: De La Salle University, Philippines

Title: The S3-symmetric tridiagonal algebra and Q-polynomial distance-regular graphs

Abstract: TBA

Preprint  |  This talk will be recorded  |  You may email the speaker for their slides

Apr 3, 10am CT

Speaker: Mark Kempton

Affiliation: Brigham Young University, USA

Title: Non-backtracking Matrices of Graphs

Abstract: Famously, the adjacency matrix of a graph can be used to enumerate walks in graphs.  This makes the adjacency spectrum important to understanding graph structure.  I will talk about the non-backtracking matrix, which is used to enumerate walks that are not allowed to backtrack.  This matrix also have interesting spectral properties, which I will discuss.  We will also look at constructions of matrices that are cospectral with respect to the non-backtracking matrix.

No preprint  |  This talk will be recorded  |  Slides will be shared

Apr 17, 10am CT

Speaker: Lord Kavi

Affiliation: Concordia University of Edmonton, Canada

Title: TBA

Abstract: 

May 1, 10am CT

Speaker: Sarojini Mohapatra

Affiliation: NIT Rourkela, India

Title: TBA

Abstract: 

May 15, 10am CT

Speaker: Domingos Cardoso

Affiliation: University of Aveiro, Portugal

Title: TBA

Abstract: 

For titles and abstracts of previous talks, and links to recordings, please visit here .

Please contact Hermie Monterde  if you have inquiries about the seminar.